[Algorithm] BOJ LCS 2 - 9252번

 

 

 

 

1. 문제 풀이

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

처음에는 일치하는 문자열을 찾아 char 배열에 저장 한 뒤 바로 출력하는 방식으로 풀어보려 했지만

구현이 복잡해져 정확히 먼저 수를 구한 뒤 가장 긴 수열을 찾아 역추적하는 방식으로 풀었다...

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

우선 1000자를 담을 수 있는 이차원배열을 0으로 초기화 한뒤 문자가 일치할 시에 이전에 일치한 개수에

1을 더해가는 방식으로 구현했다.

아래 표를 보면 일치하는 문자를 만나면 이전 인덱스의 값에 + 1을 하고

result[i][j] = result[i - 1][j - 1] + 1;

불일치 하면 그대로 i와 j 중 더 큰 값을 넣어 줌으로 긴 카운트를 이어가도록 했다.

max(result[i][j - 1], result[i - 1][j]);

표에는 나와있지 않지만 코드 상 이전 인덱스를 카운트 하기 위해 0번 인덱스는 비우고 1번 부터 배열을 채워갔다.

 

두개의 문자열 비교가 끝나면 마지막 인덱스가 곧 가장 긴 문자열의 길이가 된다.

해당 길이 만큼의 문자열 배열을 선언, 가장 긴 문자열의 인덱스를 찾는 규칙을 찾아보면

현재 인덱스의 result[i][j - 1] , result[i - 1][j] 보다 큰 숫자 일때이고 만약 result[i - 1][j] 와 현재 인덱스가 같다면 이미 해당라인은 동일한 것이 없음으로 i—로 올라가게 된다.

더할 문자를 찾았으면 배열에 문자열을 추가하고 추가한 j 열 부터는 사용할 수 없기에 len = j - 1로 변경해준다.

2. 코드

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

int main(int argc, char const *argv[])
{
	//길이를 잴 이차원 배열 0초기화
	int result[1001][1001] = ;
	char one[1001];
	char two[1001];
	cin >> one;
	cin >> two;
	int	i_len = strlen(one);
	int	j_len = strlen(two);

	for (int i = 1; i <= i_len; i++)
	{
		for (int j = 1; j <= j_len; j++)
		{
			//문자 일치할시 이전 대각선 값 + 1
			if (one[i - 1] == two[j - 1])
				result[i][j] = result[i - 1][j - 1] + 1;
			else
				result[i][j] = max(result[i][j - 1], result[i - 1][j]);
		}
	}
	cout << result[i_len][j_len] << endl;
	//역추적으로 공통 문자열 구하기
	if (result[i_len][j_len] > 0)
	{
		char	r[result[i_len][j_len] + 1];
		int z = result[i_len][j_len] - 1;
		int len = j_len;
		for (int i = i_len; i >= 0; i--)
		{
			if (result[i][len] == 0)
				break ;
			for (int j = len; j >= 0; j--)
			{
				if (result[i][j] == result[i - 1][j])
					break ;
				if (result[i][j] != result[i][j - 1])
				{
					r[z--] = two[j - 1];
					len = j - 1;
					break ;
				}
			}
		}
		r[result[i_len][j_len]] = '\0';
		cout << r << endl;
	}
	return 0;
}

 

3. 채점 기록

 

메모리 : 5812KB / 시간 : 4ms

 

 

 

---