백준 1120 풀이

링크텍스트

취약하다고 생각되는 문자열 문제이다.
문자열 문제는 내가 생각하기에 내가 문제에 대한 접근방법을 잘 몰라서 취약하다고 생각된다.
처음에 이 문제를 접했을 때 길이의 차만큼 모든 알파벳을 앞뒤로 대입해가면서 풀 생각을 했다.
그런데 이렇게 푸는 것이 너무 비효율적인 것 같고 발생할 수 있는 모든 경우의 수에 대해 대응할 수 없을 것 같았다.

그래서 생각을 조금 하다가 결국 구글로 찾아갔다. ㅠㅠ

구글에서 얻은 아이디어는 굉장했다.

길이가 다른 두 문자열의 차이를 줄이는 것이 문제의 핵심인데 이것은 결국 긴 문자열에서 같은 문자를 삽입해서 차이를 줄이면된다는 것이다.

어짜피 문자열에 문자를 삽입할 때 삽입된 문자로 인해 차이가 증가하면 안된다는 것이다.

이 아이디어에서 착안하여 문제를 슬라이딩 윈도우 기법으로 풀었다.
B문자열을 문자열의 차이만큼 substring으로 만들어 A문자열과 비교하면서 다른 문자의 개수를 구하면 답이 구해졌다.

조금만 더 생각했으면 생각해낼 수 있는 아이디어였는데 더 고민안해보고 구글로 찾아간 나 자신을 반성한다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int solution(string str1, string str2);

int main() {
	int answer = 0;
	int n;
	int m;
	string str1;
	string str2;
	cin >> str1 >> str2;
	
	int l1 = str1.length();
	int l2 = str2.length();
	int min = 1000000;

	int diff = abs(l1 - l2);
	for (int i = 0; i <= diff; i++) {
		string tmp = str2.substr(i,(l1+i));
		int dif = 0;
		for (int j = 0; j < l1; j++) {
			if (str1[j] != tmp[j]) {
				dif++;
			}
		}
		if (dif < min) {
			min = dif;
		}
	}
	answer = min;

	cout << answer << '\n';
}