[Java+Python]9251번, LCS(Longest Common Subsequence)

문제

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

 

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 

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

 

출력

 

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

풀이

 

조금 헷갈려서 시간이 들었지만, 흔하고(?) 유명한 동적계획법 문제이다.

 

먼저 두 문자열 n, m을 입력받고 (n.length + 1)(mlength + 1)크기의 이중 배열을 memo를 생성한다.

 

이어서 이중 반복문을 순회하며 n.charAt(i - 1)과 m.charAt(j - 1)이 같다면

 

memo의 값을 +1 해서 갱신해 주고, 같지 않다면 이전 탐색 값들 중 더 큰 값으로 설정한다.

 

이렇게 memo 배열을 채운 뒤 가장 마지막 값을 출력하면 완성.

 

말로 하니 좀 길지만 코드로 보면 의외로 단순하다.

 

먼저 자바 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Prob9251 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String n = br.readLine();
		String m = br.readLine();

		int[][] memo = new int[n.length() + 1][m.length() + 1];

		for (int i = 1; i <= n.length(); i++) {
			for (int j = 1; j <= m.length(); j++) {
				if (n.charAt(i - 1) == m.charAt(j - 1)) {
					memo[i][j] = memo[i - 1][j - 1] + 1;
				} else {
					memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
				}
			}
		}

		System.out.println(memo[n.length()][m.length()]);
	}
}

다음으로 파이썬 코드.

 

이중 반복문이 들어가면 파이썬 코드의 효율이 떨어지는 것 같다.

import sys

n = sys.stdin.readline().rstrip()
m = sys.stdin.readline().rstrip()

ln = len(n)
lm = len(m)

memo = [[0 for _ in range(lm + 1)] for _ in range(ln + 1)]

for i in range(1, ln + 1):
    for j in range(1, lm + 1):
        if n[i - 1] == m[j - 1]:
            memo[i][j] = memo[i - 1][j - 1] + 1
        else:
            memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])

print(memo[ln][lm])