백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 9252 LCS 2 [최장 공통 부분 수열]

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 9252 LCS 2 [최장 공통 부분 수열]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

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

9252번: LCS 2

 

 

참고 📌

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-5-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-9251-LCS

백준/ Gold 5 문제 , 백준 파이썬 9251 , LCS

 

 

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

 

 

 

 

문제풀이 소감 🧑‍💻

 

이전에 풀었던 LCS 문제와 추가 학습을 한 뒤 문제에 접근하였다.

LCS1 문제는 완성 문자의 형태를 굳이 모르고도 푸는 것이 가능했지만, 이 문제는 역추적해서 완성 문자 형태까지 출력해야하므로 좀 더 난이도 있게 느껴졌습니다.

 

 

요구사항 📋

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제

 

주의 ❗

문자는 위, 왼쪽 문자 모두 같은 것이 없을때 행에 해당하는 문자의 현재 위치 문자 정보를 추가해준다.

 

 

 

해결 전략 📝

우선, board 라는 2차원 배열에 공통 부분 수열의 길이들을 다 저장하고, 이후 맨 마지막 부터 역추적으로 0을 만날때까지  문자를 만들면서 이동한다. 

 

 

 

 

정답 💯

 

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_X, input_Y] = input.map((v) => v.trim());
function solution(X, Y) {
  const lenX = X.length;
  const lenY = Y.length;
  let [mx, my] = [lenX, lenY];
  let board = Array.from(Array(lenX + 1), () => Array(lenY + 1).fill(0));
  let result = [];

  for (let i = 1; i <= lenX; i++) {
    for (let j = 1; j <= lenY; j++) {
      if (X[i - 1] === Y[j - 1]) board[i][j] = board[i - 1][j - 1] + 1;
      else board[i][j] = Math.max(board[i - 1][j], board[i][j - 1]);
    }
  }

  while (board[mx][my] !== 0) {
    const now = board[mx][my];
    const [up, left] = [board[mx - 1][my], board[mx][my - 1]];
    if (now === up && now === left) {
      mx -= 1;
    } else if (now === up) mx -= 1;
    else if (now === left) my -= 1;
    else {
      result.push(X[mx - 1]);
      mx -= 1;
      my -= 1;
    }
  }

  console.log(board[lenX][lenY]);
  if (board[lenX][lenY] !== 0) console.log(result.reverse().join(""));
}

solution(input_X, input_Y);