1. 문제 풀이
모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
처음에는 일치하는 문자열을 찾아 char 배열에 저장 한 뒤 바로 출력하는 방식으로 풀어보려 했지만
구현이 복잡해져 정확히 먼저 수를 구한 뒤 가장 긴 수열을 찾아 역추적하는 방식으로 풀었다...
문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
우선 1000자를 담을 수 있는 이차원배열을 0으로 초기화 한뒤 문자가 일치할 시에 이전에 일치한 개수에
1을 더해가는 방식으로 구현했다.
아래 표를 보면 일치하는 문자를 만나면 이전 인덱스의 값에 + 1을 하고
result[i][j] = result[i - 1][j - 1] + 1;
C++
복사
불일치 하면 그대로 i와 j 중 더 큰 값을 넣어 줌으로 긴 카운트를 이어가도록 했다.
max(result[i][j - 1], result[i - 1][j]);
C++
복사
표에는 나와있지 않지만 코드 상 이전 인덱스를 카운트 하기 위해 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] = {0,};
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;
}
C++
복사
3. 채점 기록
메모리 : 5812KB / 시간 : 4ms
