백준 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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

 

쉬운 문제 맞는데,,, 왜 머리가 안돌아갈까...

아이디어는 더 긴 문자열 str2라고 할 때, str2에서 한 인덱스로부터 str1을 비교하는 것임

빈 부분은 어차피 str2랑 같은 걸로 채우면 차이에 포함이 안되니..

그래서 str2의 0인덱스 부터 diff 인덱스까지를 시작 가능 위치로 놓고 

차이 구한 다음에 min 구하면 끝.

 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string str1, str2;
int diff;

int main(void)
{
	

	cin >> str1 >> str2;
	diff = str2.size() - str1.size();
	int ans = 50;

	for (int i = 0; i <= diff; i++)
	{
		int count = 0;

		for (int j = 0; j < str1.size(); j++)
		{
			if (str1[j] != str2[i + j])
			{
				count++;
			}
		}

		if (ans > count)
		{
			ans = count;
		}
	}
	
	cout << ans << endl;
	
	
}