[C++] 1120번: 문자열

링크

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

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

예제 입력 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

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

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

	int correct = 0;
	int wrong = 0;

	string x, y;
	cin >> x >> y;

	for (int i = 0; i <= y.size() - x.size(); i++)
	{
		int correct_temp = 0;
		int wrong_temp = 0;

		for (int j = i; j < x.size() + i; j++)
		{
			if (x[j-i] == y[j])
				correct_temp++;
			else
				wrong_temp++;
		}

		if (correct <= correct_temp)
		{
			correct = correct_temp;
			wrong = wrong_temp;
		}
	}

	cout << wrong << endl;

	return 0;
}

풀이

• 문자열 x와 y가 주어졌을 때 x는 y보다 작거나 같다는 점을 이용하였다.
  
  

x가 붉은색, y가 검은색 글씨라고 할 때 x를 y와 비교해서 각 자리와 일치하는 글자,

틀린글자를 체크해서 갯수를 구한다.
이 때 구한 일치하는 글자가 저장된 일치하는 글자보다 많은 경우
구한 일치하는 글자 수와 틀린 글자 수를 새로 저장한다.

 

위와 같은 방식으로  y.size() - x.size() + 1 번 만큼 반복해서 주어진 문자열을 모두 탐색하도록 한다.

앞 뒤로 원하는 문자열을 넣을 수 있다는 특성 때문에 가장 많은 일치하는 글자를
남기는 구간이 가장 적은 문자열의 차이를 나타내는 구간이고 이 구간의 값이 곧 정답이 된다.

 

adaabc aababbc

위 예시에서는 

adaabc를 기준으로 할 때

aababb와 ababbc 두개의 문자열과 비교하게 되는데

ababbc 문자열이 일치하는 문자 4개, 틀린글자 2개로 가장 최선의 결과를 나타내고

정답은 2개가 된다.