백준 1120번 : 문자열

링크 : https://www.acmicpc.net/problem/1120

문제읽기

맙소사. 이어폰을 안가져왔다. 하지만 굴하지 않고 오늘은 speedy하게 접근하겠다.

길이는 같게 주어지고 문자열의 차이를 알아야 한다. 두 문자열 X와 Y의 차이는 X[i]≠Y[i]인 i의 개수이므로 인덱스로 접근하는 것이 빠를 것 같다. 배열이나 벡터. 여기서 A와 B의 길이는 최대 50으로 주어졌으므로 배열로 접근해도 무리 없을 것 같다. for문을 통한 탐색이 맞다.

A의 길이는 B의 길이보다 작거나 같고라는 조건 때문에 B의 길이가 더 길 경우 A와의 차이만큼 빼주어야 한다. -> 사족이 된다.

여기서 A와 B의 길이가 다른 경우 연산을 통해 A에 알파벳을 앞뒤로 추가할 수 있다. 당연히 B와 같게끔 만들어보자. -> 사족이 된다.

코드

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

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

	string A, B;
	cin >> A >> B;
	int Asz = A.size();
	int Bsz = B.size();
	int wrong = Bsz; 
	//A와 B의 길이는 같은 상태
	for (int i = 0; i <= (Bsz-Asz); i++) {
		int tmp = 0;
		for (int j = 0; j < Asz; j++) {
			if (A[j] != B[i + j])
				tmp++;
		}
		wrong = (tmp > wrong) ? wrong : tmp;
	}
	cout << (wrong);
	return 0;
}

분석

사실 greedy 탐색으로 진행해도 된다. 어차피 앞뒤로 알파벳을 붙이더라도 최대한 B에 맞춰 붙여지기고 가운데는 바뀌지 않기 때문에 가운데 부분의 차이가 최소화된 곳을 찾는 것이 가장 쉬운 방법이였다.