[백준 1120] 문자열

문제출처: https://www.acmicpc.net/problem/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문자열의 갯수를 일일이 찾는 문제" 를 구현한코드를 살짝 응용했다고볼 수 있습니다. 15행의 조건식이 다소 어렵다고 느껴지지만 직접 적어보면 이해가 갈 겁니다. "apple"과 "chococake" 에서 "apple" 이 "chococake"문자열 안에 포함되어있는지를 알아보는 과정을 직접 적어보시고 15행의 조건식, 18행의 조건식을 이해하기바랍니다. 그리고 문제는 차이의 최솟값을 구하므로 20~21행에서 차이를 발견하면 카운팅해주고 18행의 연산을 한번 마칠 때 마다 차이의 갯수를 가장작은값으로 초기화시켜주면되겠습니다. 

코드

#include<iostream>
#include<algorithm>
#include<string>
int arr[50];
using namespace std;
int main()
{
	string a, b;
	cin >> a >> b;
	int a_len = a.size();
	int b_len = b.size();
	//문자열의 최대길이가 50이므로 최악의경우 정답50가능
	int ans = 50;
	//하나씩 비교하며 
	for (int i = 0; i <b_len-a_len+1; i++)
	{
		int cnt = 0;
		for (int j = 0; j <a_len; j++)
		{
			//다를 떄마다 ++
			if (b[i + j] != a[j])
				cnt++;
		}
		//문제의 정답을 구하기위해 매번초기화
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}

결과