문자열

알고리즘 구분 : 구현, 문자열, 브루트포스

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

A의 앞에 아무 알파벳이나 추가한다.
A의 뒤에 아무 알파벳이나 추가한다.
이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력
첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력
A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1
adaabc aababbc
예제 출력 1
2
예제 입력 2
hello xello
예제 출력 2
1
예제 입력 3
koder topcoder
예제 출력 3
1
예제 입력 4
abc topabcoder
예제 출력 4
0
예제 입력 5
giorgi igroig
예제 출력 5
6

문제 풀이

입력받은 A의 위치를 B에 대응시켜 움직이면서, 어디 있을 때, 가장 최소의 값을 가지는지 찾으면 된다. 이를 이중반복문을 사용하면 되며, 첫 번째 반복문은 A의 시작 위치를 지정하기 위한 범위의 반복문, 두 번재 반복문은 A길이만큼 순회하며, B와 비교하여 불일치 경우의 수를 카운트하는 반복문이다.
이렇게 진행하면 되는 이유는, 앞 뒤로 추가할 때, 어느 알파벳을 추가해도 된다라고 했기에, 무조건 일치할 수 있다라는 것을 알 수 있기 때문이다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

string a, b;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> a >> b;
	
	solve();
	
	return 0;
}

void solve() {
	int minNum = 987654321;
	for(int i = 0; i < b.length() - a.length() + 1; i++) {
		int cnt = 0;
		
		for(int j = 0; j < a.length(); j++) {
			if(a[j] != b[j + i]) {
				cnt++;
			}
		}
		
		minNum = min(minNum, cnt);
	}
	
	cout << minNum << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/1120
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.