[백준 1120] 문자열 (C++)

문제

---

길이가 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를 만든다고 생각하는 것보다 B의 앞이나 뒤를 지워 A의 길이만큼의 문자열을 만든다고 생각하면 쉽다. 그럼 B의 처음부터 끝까지 A의 길이만큼 잘라내어 해당 문자열과 A를 비교해주면 된다. A의 길이만큼 잘라내면 해당 경우에 대해 앞 뒤로 남은 문자들이 A로부터 추가되는 문자가 되어야 최솟값을 가질 수 있기 때문이다. 따라서 모든 경우에 대해 substr()로 얻어낸 문자열과 A를 비교한 최솟값이 답이 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str1, str2;
	int answer = 51;
	cin >> str1 >> str2;
	for (int i = 0; i <= str2.length() - str1.length(); i++)
	{
		string str = str2.substr(i, str1.length());
		int count = 0;
		for (int j = 0; j < str.length(); j++)
		{
			if (str1[j] != str[j])
			{
				count++;
			}
		}
		answer = min(answer, count);
	}
	cout << answer << "\n";
	return 0;
}