[LeetCode] 1143. Longest Common Subsequence

임혁진·2022년 10월 26일

알고리즘

목록 보기

51/64

1143. Longest Common Subsequence

문제링크:https://leetcode.com/problems/longest-common-subsequence/

두 문자열에 존재하는 common subsequence의 최대 길이를 구하는 문제다. Subsequence는 기존 문자열의 순서는 유지하되 일부 문자를 제외해 얻을 수 있는 부분문자열이다.

Solution

1. Dynamic programming

두 개의 문자열을 비교하기 위해 2 pointers와 DP 두가지 방법을 고려했다. 2 pointers를 이용할 경우 greedy하게 문제를 해결해야 하는데 문제는 "ddddabcef", "abcddddef"와 같은 문자열의 경우 앞의 dddd를 처음 무시하게 되면 정확한 결과가 나오지 않는다. 따라서 과거의 데이터를 다시 끌어내서 연산에 사용하기 위한 DP가 적합한 알고리즘이라고 생각되었다.

두 개의 데이터를 DP알고리즘으로 적용하기 위해 mem[i][j]를 text1[0~i], text2[0~j]의 subsequence최대 길이라고 가정했다. mem[i][j]를 결정하는 요소는 기존 완성된 subsequence를 그대로 유지하는 방법과 새로 추가된 문자로 인해 subsequence의 길이가 늘어나는 방법이다. 전자의 경우 Math.max(mem[i-1][j], mem[i][j-1]), 후자의 경우 text1[i] === text2[j] 일 때, mem[i-1][j-1] + 1 이 된다. 이것을 아까 고려한 "ddddabcef", "abcdddef"예시에서 풀어보면 다음과 같다.

	d	d	d	d	a	b	c	e	f
a	0	0	0	0	1*	1	1	1	1
b	0	0	0	0	1	2*	2	2	2
c	0	0	0	0	1	2	3*	3	3
d	1*	1*	1*	1*	1	2	3	3	3
d	1*	2*	2*	2*	2	2	3	3	3
d	1*	2*	3*	3*	3	3	3	3	3
d	1*	2*	3*	4*	4	4	4	4	4
e	1	2	3	4	4	4	4	5*	5
f	1	2	3	4	4	4	4	5	6*

*표시한 부분이 text1[i] === text2[j] 인 부분으로 mem[i-1][j-1] + 1 을 하는 부분으로 왼대각선 값의 + 1이다. 나머지 부분은 주변 위와 왼쪽 데이터 중 큰 값을 가져온다. 최종적으로 6을 반환한다.

Algorithm

DP를 할 mem배열을 만든다.
getMemIJ는 i와 j의 범위를 확인해 벗어날 경우 0을 반환한다.
DP를 처음부터 반복한다. 마지막 값을 구하기 위해선 모든 구간을 반복해야한다.
mem[i][j]값은 text1[i] === text2[j]인 경우 대각선의 값을 가져오고 아닌 경우엔 주변 값 중 큰 값을 가져온다.
모든 mem값을 구한 후 최종값을 반환한다.

var longestCommonSubsequence = function(text1, text2) {
  // Common subsequence를 구해야 한다.
  // DP
  const mem = [];
  for (let i = 0; i < text1.length; i++) {
    mem.push(new Array(text2.length));
  }
  // mem[i][j] : text1(0~i) text2(0~j) subsequence length
  // mem[i][j] = text1[i] === text2[j] ? mem[i-1][j-1] + 1 : Math.max(mem[i][j-1], mem[i-1][j]);
  const getMemIJ = (i, j) => {
    if (i < 0 || j < 0) return 0;
    else return mem[i][j];
  }
  for (let i = 0; i < text1.length; i++) {
    for (let j = 0; j < text2.length; j++) {
      mem[i][j] = (text1[i] === text2[j])
        ? getMemIJ(i-1, j-1) + 1 // 같은 경우 + 1
      	: mem[i][j] = Math.max(getMemIJ(i-1, j), getMemIJ(i, j-1)); // 다른 경우 주변값 유지
    }
  }
  return mem[text1.length - 1][text2.length - 1];
};

O(n^2) 시간 복잡도와, O(n^2) 공간 복잡도를 필요로한다. DP를 모든 구간에서 반복하는데 데이터는 왼쪽대각, 위, 왼쪽 데이터만 필요로 하고 결과는 마지막만 있으면 된다는 점을 이용한다면 공간 복잡도를 줄일 수 있다고 판단했다.

2. Dynamic programming O(n) space

Full iteration을 하는 과정에서 mem[i][j]는 mem[i-1][j-1], mem[i-1][j], mem[i][j-1]의 값만 필요하다. 따라서 모든 데이터를 저장하지 않고 한 행만 임시로 저장하고 매번 갱신한다면 O(n)의 공간으로 구현할 수 있을 것으로 보인다.

Algorithm

DP로 이전 행을 저장할 부분은 tempMem으로 초기값으로 0을 저장한다.
다음 행을 계산한 결과는 newMem에 저장하고 모든 값을 얻은 후 tempMem 을 newMem 배열로 갱신하고 다음 행을 계산한다.
모두 계산한 후 tempMem의 끝 값을 결과로 반환한다.

var longestCommonSubsequence = function(text1, text2) {
  // Common subsequence를 구해야 한다.
  // DP
  // mem[i][j] : text1(0~i) text2(0~j) subsequence length
  // mem[i][j] = text1[i] === text2[j] ? mem[i-1][j-1] + 1 : Math.max(mem[i][j-1], mem[i-1][j]);
  
  const len1 = text1.length, len2 = text2.length;
  let tempMem = new Array(len2).fill(0); // mem[i-1]만 임시로 가지고 잇어도 full dp가 가능함
  for (let i = 0; i < len1; i++) {
    const newMem = []; // mem[i]
    for (let j = 0; j < len2; j++) {
      newMem[j] = (text1[i] === text2[j]) 
        ? (tempMem[j-1] ?? 0) + 1 
        : Math.max(tempMem[j], (newMem[j-1] ?? 0));
    }
    tempMem = newMem; // mem[i-1]로 갱신
  }
  return tempMem[len2 - 1];
};