1120_문자열_그리디 알고리즘

https://www.acmicpc.net/problem/1120

1120번: 문자열

문제

  길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

  두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

  이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

  첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

  A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

---

문제 이해

  두 문자열의 차이는 문자 배열의 자리에 위치하는 알파벳이 다른 경우를 뜻한다. 이러한 조건에서 문자열 A와 B를 줌으로써 A를 B의 길이와 동일하게 만들면서 문자열의 차이를 최소화하는 문제인 것 같다.

문제 해결

  1. 앞에 문자를 추가해야하는 경우

  2. 뒤에 문자를 추가해야하는 경우

 

  이 두 갈래로 문제를 나눌 수 있다. 그렇다면 그냥 문자열 A를 문자열 B에 대칭해보며 가장 차이가 작은 값이 나올 때를 기준으로 문자열의 앞뒤가 비는만큼 계산하면 되는 것 아니냐라는 생각이 들었다. 

 

#include <iostream>
#include <algorithm>
#define INF 123456789

using namespace std;

string A, B;
int res = INF, minV;

int main(void) {
	cin >> A >> B;
	for(int i = 0; i <= B.length() - A.length(); i++) {
		minV = 0;
		for(int j = 0; j < A.length(); j++) {
			if(B[i + j] != A[j]) {
				minV++;
			}
		}
		res = min(minV, res);
	}
	cout << res << '\n';
	return 0;
}