모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
처음에는 일치하는 문자열을 찾아 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로 변경해준다.