acmicpc.net 1120 문자열(c++)

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의 길이가 같아질 때 까지 다음과 같은 연산을 할 수 있다.

A의 앞에 아무 알파벳이나 추가한다.

A의 뒤에 아무 알파벳이나 추가한다.

이 때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

 

입력

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

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력  

adaabc aababbc

예제 출력  

2

방법론.

뭘 출력하라는건지 자세히 안써있는데 a와 b의 길이가 같게했을때 차이의 최솟값을 출력하는 프로그램이다. 위의 예제같은경우 왼쪽 문자열 맨앞에 a를 덧붙인다고 하면 aadaabc가 되고, 뒤는 aababbc이다.

이 두 문자열의 차이는 2이다. 이걸 출력하는건데 최솟값을 출력하면 되고, 앞쪽의 문자열이 더 짧다.

앞이나 뒤는 어떤 문자열이든 붙일 수 있으므로 그냥 문자열 앞에 하나씩 아무거나 붙인다고 가정하고 인덱스를 증가시켜가면서 하나씩 비교한후 차이가 가장 적을 경우를 출력하면 된다.

c++코드. 파이썬 코드로 변환해도 비슷하기에 c++만 적어놓음.

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

int main(){
	int d,min = 99999;
	string a,b;
	cin>>a>>b;
	for(int i=0;i<=b.length()-a.length();i++)
	{
		d = 0;
		for(int j=0;j<a.length();j++)
		{
			if(a[j]!=b[i+j])
				d++;
		}
		if(min > d)
			min = d;
	}
	cout<<min;
    return 0;
}