[PS 백준 - 1.10] 1120번: 문자열

문제 정보

백준 1120번 - 바로가기

• 난이도: 실버 4
• 알고리즘: 문자열

---

코멘트

먼저 s1이 더 짧은 문자열이 되도록 하였고, 추가 / 삭제가 가능하다는 조건은 두 문자열의 차이에는 아무 영향을 끼치지 않기 때문에 내부 문자열만 가지고 생각했다.

1. 짧은 문자열을 긴 문자열의 맨 왼쪽에 배치한 채로 차이가 얼마인지를 구한다.
2. 짧은 문자열을 한칸 오른쪽으로 옮겨서 긴 문자열과 차이를 구한다.
3. 이런 식으로 긴 문자열의 맨 오른쪽과 짧은 문자열의 맨 오른쪽이 겹쳐질 때까지 차이를 구한다.
4. 그 차이들 중에서 가장 작은 것을 출력한다.

---

소스 코드

#include <iostream>

using namespace std;

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

	string s1, s2;
	cin >> s1 >> s2;

	int len1 = s1.length();
	int len2 = s2.length();

	// 무조건 s1이 더 짧게
	if (len1 > len2) {
		string temp = s2;
		s2 = s1;
		s1 = temp;
		len1 = s1.length();
		len2 = s2.length();
	}

	int min = 51;
	int diff = 0;
	for (int i = 0; i <= len2 - len1; i++) {
		for (int j = i; j < i + len1; j++) {
			if (s1[j-i] != s2[j]) diff++;
		}
		min = (min < diff) ? min : diff;
		diff = 0;
	}
	cout << min;
}