JS Coding Blog

겹쳐 붙여 만드는 최단 배너

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

today hard bitmask-dp 함수명: solution 제한 시간: 400ms

문자열 조각 배열 chunks가 주어질 때, 모든 조각을 부분 문자열로 포함하는 가장 짧은 문자열을 반환하는 solution 함수를 작성하세요.

길이가 같은 정답이 여러 개라면 사전순으로 가장 앞서는 문자열을 반환하세요.

예를 들어 ['ABC', 'BCA', 'CAB']라면 ABCAB 안에 세 조각이 모두 포함되므로 가능한 정답입니다. 이보다 더 짧은 문자열은 만들 수 없으므로 ABCAB를 반환해야 합니다.

제한사항

  • chunks는 길이 1 이상 12 이하의 문자열 배열입니다.
  • 각 문자열은 길이 1 이상 20 이하입니다.
  • 문자열은 영문 대문자로만 이루어집니다.
  • 같은 문자열이 여러 번 들어올 수 있습니다.
  • 어떤 문자열이 다른 문자열의 부분 문자열이라면, 더 긴 문자열에 이미 포함되므로 따로 이어 붙일 필요가 없습니다.
  • 반환값은 모든 조각을 부분 문자열로 포함하는 최단 문자열입니다.
  • 최단 길이 정답이 여러 개라면 사전순으로 가장 앞서는 문자열을 반환해야 합니다.

예시

  • 입력: ["ABC", "BCA", "CAB"] → 출력: "ABCAB"
  • 입력: ["GATT", "TTACA", "TAC", "ACA"] → 출력: "GATTACA"
  • 입력: ["AX", "XB", "AY"] → 출력: "AYXB"
  • 입력: ["CODE", "ODE", "DE", "E"] → 출력: "CODE"

힌트

  • 먼저 다른 문자열 안에 완전히 포함되는 조각들을 제거하면 상태 수를 줄일 수 있습니다.
  • 두 문자열을 이어 붙일 때, 앞 문자열의 suffix와 뒤 문자열의 prefix가 최대한 많이 겹치도록 합칠 수 있습니다.
  • 마지막에 어떤 조각으로 끝났는지까지 포함해서 상태를 관리하면 비트마스크 DP를 설계하기 쉽습니다.

해설

이 문제는 겉보기에는 문자열 구현처럼 보이지만, 핵심은 조각 사이의 겹침(overlap)을 미리 계산한 뒤 순서를 최적화하는 것입니다.

1) 포함되는 조각 먼저 제거하기

예를 들어 ODE, DE, E는 모두 CODE 안에 포함됩니다. 이 조각들을 그대로 두면 같은 정보를 여러 번 상태에 넣게 되어 비효율적입니다.

따라서 먼저:

  1. 중복 문자열을 제거하고
  2. 어떤 문자열이 다른 문자열의 부분 문자열이면 제거합니다.

이 전처리만 해도 실제로 DP가 처리해야 할 문자열 수가 크게 줄어듭니다.

2) 두 조각 사이의 최대 겹침 길이 계산하기

문자열 a 뒤에 b를 붙일 때는, a의 뒤쪽과 b의 앞쪽이 최대한 겹치면 전체 길이를 줄일 수 있습니다.

예를 들어:

  • a = "ABC"
  • b = "BCA"

이면 "BC"가 겹치므로 단순히 "ABCBCA"로 붙이지 않고 "ABCA"로 합칠 수 있습니다.

이 겹침 길이를 모든 (a, b) 쌍에 대해 미리 계산해 두면, 나중에 a 다음에 b를 붙였을 때 새로 늘어나는 문자열은 b.slice(overlap[a][b])만 보면 됩니다.

3) 비트마스크 DP

전처리 후 남은 문자열 수를 n이라고 하면, 어떤 문자열들을 이미 사용했는지를 mask 비트마스크로 나타낼 수 있습니다.

dp[mask][last]를

  • mask에 포함된 문자열들을 모두 사용했고
  • 마지막 문자열이 last일 때
  • 만들 수 있는 최적의 결과 문자열 이라고 정의합니다.

상태 전이는 다음과 같습니다.

  • 아직 쓰지 않은 문자열 next를 고른다.
  • 현재 결과 뒤에 next의 겹치지 않는 부분만 이어 붙인다.
  • 길이가 더 짧으면 갱신한다.
  • 길이가 같다면 사전순으로 더 앞서는 문자열을 선택한다.

4) 왜 hard인가?

그리디하게 “가장 많이 겹치는 것부터 붙이기”만 해서는 항상 최적해가 나오지 않습니다. 지역적으로 가장 좋은 선택이 전체 순서에서는 손해가 될 수 있기 때문입니다.

그래서 이 문제는:

  • 문자열 전처리
  • 쌍별 overlap 계산
  • 부분집합 상태 탐색
  • 길이 우선, 사전순 보조 비교 를 함께 다뤄야 해서 hard 난이도에 가깝습니다.

5) 시간 복잡도

전처리 후 문자열 수를 n, 각 문자열 최대 길이를 L이라고 하면:

  • 포함 여부 / overlap 계산: 대략 O(n^2 * L^2) 이내
  • DP: O(2^n * n^2)

제한에서 n <= 12이므로 비트마스크 DP로 충분히 처리할 수 있습니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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