[C언어] 1120번

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

 

---

이 문제는 아래와 같은 방법을 사용하여 해결할 수 있다.

 

" 문자열 b와 문자열 a의 차이가 가장 작을 때의 값을 찾는다. "

 

위와 같은 방법이 가능한 이유는 다음과 같다.

문제를 살펴보면, 문자열 a의 앞, 뒤에 새로운 문자를 추가할 수 있다고 한다. 즉 이것은 문자열 b와 동일한 문자를 추가할 수 있다는 뜻이므로, 기존의 문자열에서 차이의 최솟값을 구하라는 것을 의미한다고 볼 수 있다.

 

#include <stdio.h>
#include <string.h>

int main(void) {
	int i, j;
	char a[51], b[51];

	scanf("%s %s", &a, &b);

	int min = strlen(b);

	for (i = 0; i <= strlen(b) - strlen(a); i++) {
		int tmp = 0, cnt = 0;

		for (j = i ; j < i + strlen(a); j++) {
			if (a[cnt] != b[j])
				tmp++;

			cnt++;
		}
		
		if (min > tmp)
			min = tmp;
	}

	printf("%d\n", min);

	return 0;
}