[백준 17218] 비밀번호 만들기 (C++)

문제

---

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

---

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

---

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

 

문제 풀이

---

최장 공통부분문자열 문제. dp를 이용한다.

 

두번째 문자열의 i번째 인덱스 문자와 첫번째 문자열의 j번째 인덱스 문자까지 판별했을 때, 최대 길이를 저장하는 2차원 dp 배열을 만든다.

만약 두번째 문자열의 i번째 문자와 첫번째 문자열의 j번째 문자가 같다면 두번째 문자열의 i-1번째 문자와 첫번째 문자열의 j-1번째 문자열까지의 최댓값에 1을 더해주면 된다. dp[i][j] = dp[i-1][j-1]+1

두번째 문자열의 i번째 문자와 첫번째 문자열의 j번째 문자가 다르다면 두번째 문자열의 i-1번째 문자와 첫번째 문자열의 j번째 문자까지 판별한 값과, 두번째 문자열의 i번째 문자와 첫번째 문자열의 j-1번째 문자까지 판별한 값을 비교해 더 큰 값을 채워주면 된다. dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

이전 행의 데이터를 가져오므로 (M+1)*(N+1) 크기의 배열을 생성한 후 첫번째 행과 각 행의 첫번째 열은 인덱스 에러 방지를 위해 비워두고 0으로 초기화해둔다. (단, 첫번째 문자열의 길이가 N, 두번째 문자열의 길이가 M.)

 

dp 배열을 채웠으면 이를 바탕으로 어떤 문자가 나왔을 때 가장 긴 공통 부분 문자열을 만들 수 있는지 확인한다. 처음은 i를 M으로, j를 N으로 초기화해두고 역으로 탐색해내갈 것이다.

i번째 문자와 j번째 문자가 같다면 i번째 문자와 j번째 문자 이전의 문자열에서 가장 긴 문자열의 길이를 가져와 거기에 1을 더해줬다. 따라서 현재 상태일 때 공통 부분 문자열을 이루는 문자가 들어 있고, 이를 스택에 넣어둔다. dp[i][j] = dp[i-1][j-1]+1로 식을 세워두었으므로 i와 j를 각각 1 감소시켜준다.

i번째 문자와 j번째 문자가 다르다면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 dp 배열을 채웠다. 따라서 다음으로 이동할 칸은 dp[i-1][j]와 dp[i][j-1]의 크기에 따라 달라진다. 크기에 따라 i를 1 감소시켜주거나, j를 1 감소시켜준다.

첫번째 행과 각 행의 첫번째 열은 인덱스 에러 방지를 위해 0으로 초기화해두었으므로 실제 문자열에 따른 데이터가 아니다. 따라서 i와 j 둘 중 하나라도 0에 도달하면 탐색을 종료하면 된다.

 

스택에 저장되어있는 모든 값을 꺼내 출력하면 정답이다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str1;
	string str2;
	cin >> str1;
	cin >> str2;
	int N = str1.length();
	int M = str2.length();
	int** dp = new int*[M+1];
	for (int i = 0; i < M+1; i++)
	{
		dp[i] = new int[N+1];
		for (int j = 0; j < N+1; j++)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i < M+1; i++)
	{
		for (int j = 1; j < N+1; j++)
		{
			if (str2[i-1] == str1[j-1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j-1]);
			}
		}
	}
	int i = M;
	int j = N;
	stack<char> s;
	while (i > 0 && j > 0)
	{
		if (str2[i - 1] == str1[j - 1])
		{
			s.push(str2[i - 1]);
			i--;
			j--;
		}
		else
		{
			if (dp[i-1][j] < dp[i][j-1])
			{
				j--;
			}
			else
			{
				i--;
			}
		}
	}
	while (!s.empty())
	{
		cout << s.top();
		s.pop();
	}
	return 0;
}