Question
두 문자열을 입력받아 다음의 조건을 만족하는 LCS*의 길이를 리턴해야 합니다.
•
LCS: 두 문자열에 공통으로 존재하는 연속되지 않는 부분 문자열(Longest Common Subsequence)
•
문자열 'abc'의 subseqeunce는 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' 입니다.
입력
인자 1 : str1
•
string 타입의 알파벳 소문자와 숫자로 이루어진 문자열
•
str1.length는 50 이하
인자 2 : str2
•
string 타입의 알파벳 소문자와 숫자로 이루어진 문자열
•
str2.length는 50 이하
출력
•
number 타입을 리턴해야 합니다.
주의사항
•
LCS의 길이를 리턴해야 합니다.
•
LCS가 존재하지 않는 경우, 0을 리턴해야 합니다.
Test Case 1
let output = LCS('abcd', 'aceb');
console.log(output); // --> 2 ('ab' or 'ac')
Shell
복사
Test Case 2
output = LCS('acaykp', 'capcak');
console.log(output); // --> 4 ('acak')
Shell
복사
Solve
const LCS = function (str1, str2) {
// str1을 차례대로 돈ㅏ
// str2를 돌면서 값과 일치하는지 확인
// 일치하면 stack .push
// 일치하지 않으면 다음 str2 넘어가기
let count = 0;
let idx1 = 0;
const stack = [];
while (str1.length > idx1) {
for (let i = 0; i < str2.length; i++) {
if (str1[idx1] === str2[i]) {
stack.push(str1[idx1]);
str2 = str2.slice(i + 1);
break;
}
}
idx1++;
}
return stack.length;
};
JavaScript
복사
실행시간 : ms
// dynamic programming: O(M * N)
// memoization을 활용해 중복 계산되는 문제를 제거한다.
// LCS('ABCD', 'ACEB')의 경우 재귀 호출을 적어보면 아래와 같다.
// => 1) LCS('BCD', 'CEB')
// => 1-1) LCS('CD', 'CEB'), 1-2) LCS('BCD', 'EB')
// => 1-1-1) LCS('D', 'CEB'), 1-1-2) LCS('CD', 'EB')
// => 1-2-1) LCS('CD', 'EB'), 1-2-2) LCS('BCD', 'B')
// 더 볼 필요 없이 1-1-2)와 1-2-1)은 같은 문제임을 알 수 있다.
const LCS = function (str1, str2) {
const M = str1.length;
const N = str2.length;
const memo = [];
// 중복 계산을 방지하기 위해 left, right
for (let i = 0; i < M + 1; i++) memo.push(Array(N + 1).fill(-1));
const compareOneByOne = (left, right, len) => {
if (memo[left][right] !== -1) return memo[left][right];
if (left === str1.length || right === str2.length) return 0;
if (str1[left] === str2[right]) {
memo[left][right] = 1 + compareOneByOne(left + 1, right + 1, len + 1);
return memo[left][right];
}
memo[left][right] = Math.max(
compareOneByOne(left + 1, right, len), //
compareOneByOne(left, right + 1, len)
);
return memo[left][right];
};
return compareOneByOne(0, 0, 0);
};
JavaScript
복사
실행시간 : ms