[백준 17218 - Node.js] 비밀번호 만들기

문제 링크

https://www.acmicpc.net/problem/17218

17218번: 비밀번호 만들기

풀이

const [ first, second ] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const dp = [...Array(first.length + 1)].map(() => Array(second.length + 1).fill(0));

for (let i = 1; i <= first.length; i++) {
  for (let j = 1; j <= second.length; j++) {
    if (first[i - 1] === second[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
}

const output = [];
let i = first.length;
let j = second.length;
const maxLen = dp[i][j];
while (output.length < maxLen) {
  if (dp[i - 1][j] === dp[i][j]) {
    i--;
  } else if (dp[i][j - 1] === dp[i][j]) {
    j--;
  } else {
    output.push(first[i - 1]);
    i--;
    j--;
  }
}

console.log(output.reverse().join(''));

이 문제는 전형적인 최장 공통 부분 수열 문제다.

부분 수열의 길이가 아닌, 부분 수열 자체를 구하는 문제이므로,

dp 테이블을 다 채운 후에 가장 마지막 칸에서부터 역으로 거슬러 올라가야 한다.

이러한 최장 공통 부분 수열의 기본 개념에 대해서는 아래 링크를 참고하면 이해할 수 있을 것이다.

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence