백준 1120 문자열 풀이(c++)

문제

길이가 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의 문자중 몇번째부터가 가장 유사한지 체크한후 B의 앞부분을 붙이고 A를 붙이고 뒷부분을 붙이고 그 문자열을 B랑 비교하였다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
	string strA;
	string strB;
	string strTemp;
	int iCount = 0;
	int Dif = 0;
	int iMaxSame = 0;
	int Start = 0;

	cin >> strA >> strB;

	if (strA.size() == strB.size())
	{
		for (int i = 0; i < strA.size(); ++i)
		{
			if (strA[i] != strB[i])
			{
				iCount++;
			}
		}

		cout << iCount;
		return 0;
	}

	Dif = strB.size() - strA.size();

	for (int i = 0; i <= Dif; ++i)
	{
		iCount = 0;
		for (int j = 0; j < strA.size(); ++j)
		{
			if (strA[j] == strB[i + j])
			{
				++iCount;
			}
		}
		if (iMaxSame < iCount)
		{
			iMaxSame = iCount;
			Start = i;
		}
	}

	for (int i = 0; i < Start; ++i) // B에서 앞부분 붙여줌
	{
		strTemp += strB[i];
	}

	for (int i = 0; i < strA.size(); ++i)// A를 붙여줌

	{
		strTemp += strA[i];
	}

	for (int i = strTemp.size(); i < strB.size(); ++i) //뒷부분 붙여줌
	{
		strTemp += strB[i];
	}
	iCount = 0;
	for (int i = 0; i < strB.size(); ++i) //차이를 카운팅함
	{
		if (strB[i] != strTemp[i])
			++iCount;
	}

	cout << iCount;

	return 0;
}