JS Coding Blog

두 기록의 공통 배지 순서 길이

자바스크립트 코딩테스트 문제로 lcs-dp 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium lcs-dp 함수명: longestCommonBadgeSubsequence 제한 시간: 300ms

두 배지 기록에서 순서를 유지하며 공통으로 남길 수 있는 가장 긴 배지 개수를 구해 보세요.

문제 설명

문자열 배열 recordA와 recordB가 주어집니다.

각 배열은 어떤 사용자가 받은 배지 기록을 시간 순서대로 담고 있습니다. 두 기록에서 일부 배지를 지울 수 있을 때, 양쪽에 같은 순서로 남길 수 있는 배지 개수의 최댓값을 반환하는 longestCommonBadgeSubsequence 함수를 작성하세요.

남기는 배지들은 원래 기록에서 서로 떨어져 있어도 됩니다. 다만 상대적인 순서는 바뀌면 안 됩니다.

예를 들어 recordA = ["A", "B", "C", "D", "E"], recordB = ["B", "D", "E"]라면 ["B", "D", "E"]를 그대로 공통으로 남길 수 있으므로 답은 3입니다.

제한사항

  • 0 <= recordA.length <= 1000
  • 0 <= recordB.length <= 1000
  • 각 배지 이름은 길이 1 이상 20 이하의 문자열입니다.
  • 배지 이름은 대소문자를 구분합니다.
  • 반환값은 두 기록의 최장 공통 부분수열 길이입니다.
  • 공통으로 남기는 배지는 연속될 필요가 없지만, 각 기록 안에서의 순서는 유지해야 합니다.

예시

  • 입력: recordA = ["A", "B", "C", "D", "E"], recordB = ["B", "D", "E"] -> 출력: 3
  • 입력: recordA = ["red", "blue", "red", "green"], recordB = ["red", "red", "green"] -> 출력: 3
  • 입력: recordA = [], recordB = ["A", "B"] -> 출력: 0
  • 입력: recordA = ["scan", "pack", "ship"], recordB = ["scan", "ship", "pack"] -> 출력: 2

힌트

  • 두 기록의 앞에서부터 i개, j개만 봤을 때의 답을 생각해 보세요.
  • 마지막 배지가 서로 같다면 그 배지를 공통 순서의 마지막에 붙일 수 있습니다.
  • 마지막 배지가 다르다면 한쪽 마지막 배지를 포기하는 두 경우 중 더 긴 쪽을 선택해야 합니다.

해설

이 문제는 최장 공통 부분수열, 즉 LCS를 연습하는 전형적인 동적 계획법 문제입니다.

dp[i][j]를 recordA의 앞 i개와 recordB의 앞 j개만 봤을 때 만들 수 있는 최장 공통 부분수열 길이라고 두겠습니다.

두 구간의 마지막 배지를 비교합니다.

recordA[i - 1] === recordB[j - 1]

두 값이 같다면 이 배지를 공통 순서의 마지막에 붙일 수 있습니다. 따라서 이전 구간의 답에 1을 더합니다.

dp[i][j] = dp[i - 1][j - 1] + 1

두 값이 다르다면 마지막 배지 두 개를 동시에 쓸 수 없습니다. recordA 쪽 마지막 배지를 포기한 경우와 recordB 쪽 마지막 배지를 포기한 경우 중 더 큰 값을 고릅니다.

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

i나 j가 0인 경우는 한쪽 기록이 비어 있으므로 답이 항상 0입니다.

전체 DP 표를 만들어도 되지만, 현재 행을 계산할 때 필요한 값은 바로 이전 행과 현재 행의 왼쪽 값뿐입니다. 그래서 길이가 recordB.length + 1인 배열 두 개만 번갈아 쓰면 공간을 줄일 수 있습니다.

  1. prev와 curr 배열을 모두 0으로 시작합니다.
  2. recordA를 한 칸씩 늘려 가며 recordB 전체와 비교합니다.
  3. 두 배지가 같으면 prev[j - 1] + 1을 사용합니다.
  4. 다르면 prev[j]와 curr[j - 1] 중 큰 값을 사용합니다.
  5. 한 행 계산이 끝나면 curr를 다음 반복의 prev로 넘깁니다.

시간 복잡도는 두 기록의 모든 조합을 한 번씩 비교하므로 O(recordA.length * recordB.length)입니다. 공간 복잡도는 두 행만 보관하면 되므로 O(recordB.length)입니다.

연속 부분 문자열과 달리, 부분수열은 중간 원소를 건너뛸 수 있습니다. 이 차이를 DP 상태로 익히는 것이 이 문제의 핵심입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.