JS Coding Blog

금지 패턴을 피하는 이진 방송 문자열 수

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

today hard matrix-exponentiation 함수명: countSafeBinaryBroadcasts 제한 시간: 1200ms

길이가 매우 큰 이진 문자열 중 금지 패턴을 하나도 포함하지 않는 경우의 수를 세는 문제입니다.

문제 설명

길이 length인 이진 문자열을 만들려고 합니다. 각 문자는 '0' 또는 '1'만 사용할 수 있습니다.

금지 패턴 목록 bannedPatterns가 주어질 때, 이 문자열 안에 금지 패턴 중 하나라도 연속 부분 문자열로 등장하면 안 됩니다.

함수 countSafeBinaryBroadcasts(length, bannedPatterns)는 조건을 만족하는 이진 문자열의 개수를 1_000_000_007로 나눈 나머지로 반환하세요.

제한사항

  • 0 <= length <= 1,000,000,000
  • 1 <= bannedPatterns.length <= 20
  • 각 금지 패턴의 길이는 1 이상 20 이하입니다.
  • 각 금지 패턴은 '0', '1'로만 이루어집니다.
  • 같은 금지 패턴이 여러 번 주어질 수 있습니다.
  • 반환값은 1_000_000_007로 나눈 나머지입니다.

예시

  • 입력: length = 3, bannedPatterns = ["00"] → 출력: 5
  • 입력: length = 4, bannedPatterns = ["01", "10"] → 출력: 2
  • 입력: length = 5, bannedPatterns = ["000", "111"] → 출력: 16
  • 입력: length = 2, bannedPatterns = ["0", "1"] → 출력: 0
  • 입력: length = 0, bannedPatterns = ["00", "11"] → 출력: 1

첫 번째 예시에서 길이 3의 이진 문자열은 총 8개입니다. 이 중 00을 포함하는 문자열은 000, 001, 100 세 개이므로, 정답은 8 - 3 = 5입니다.

두 번째 예시에서는 01과 10이 모두 금지되어 있으므로, 문자열 안에서 값이 한 번이라도 바뀌면 안 됩니다. 따라서 가능한 문자열은 0000, 1111 두 개뿐입니다.

힌트

  • 어떤 접두 문자열을 읽었을 때, 앞으로 중요한 것은 전체 문자열이 아니라 “지금 끝부분이 금지 패턴들의 어떤 접두사와 맞물려 있는가”입니다.
  • 여러 금지 패턴을 한 번에 처리하려면 트라이와 실패 링크를 합친 자동자를 떠올려 보세요.
  • 길이가 아주 크므로 dp[i][state]를 i = 0부터 끝까지 직접 채우는 방식은 버거울 수 있습니다.

해설

이 문제의 핵심은 문자열 생성 과정을 상태 전이 문제로 바꾸는 것입니다.

1) 금지 패턴들을 자동자 상태로 압축하기

금지 패턴이 여러 개 있을 때, 지금까지 만든 문자열의 끝부분이

  • 어떤 금지 패턴의 접두사와 얼마나 맞아 있는지 만 알면 다음 문자를 붙였을 때 위험한지 판단할 수 있습니다.

이 상태 압축을 위해 bannedPatterns로 트라이를 만들고, 실패 링크까지 붙인 Aho-Corasick 자동자를 구성합니다.

각 상태는 “현재까지 읽은 문자열의 접미사 중, 금지 패턴들의 접두사와 가장 길게 맞는 상태”를 뜻합니다.

2) 금지 상태 전파하기

어떤 상태 자체가 금지 패턴의 끝일 수도 있고, 실패 링크를 따라가다가 금지 패턴의 끝을 만나도 이미 금지 문자열을 포함한 것입니다.

그래서 단순히 “직접 패턴이 끝나는 노드”만 막으면 부족합니다. 각 상태에 대해

  • 자신이 패턴 끝인지
  • 실패 링크를 따라간 조상 중 패턴 끝이 있는지 를 모두 반영해서 terminal 상태를 표시해야 합니다.

이 terminal 상태에 도달하는 모든 전이는 사용할 수 없습니다.

3) 전이 행렬 만들기

금지되지 않은 상태들만 남겨 두고, 각 상태에서 문자 '0', '1'을 붙였을 때 이동하는 다음 상태를 계산합니다.

만약 다음 상태도 안전하다면,

  • state -> nextState로 가는 경우의 수 1개 를 전이 행렬에 기록할 수 있습니다.

이렇게 하면 길이 1 증가가 곧 행렬 한 번 곱하기가 됩니다.

4) 왜 행렬 거듭제곱이 필요한가?

보통은

  • dp[i + 1][nextState] += dp[i][state] 로 길이 length까지 진행합니다.

하지만 length가 최대 1,000,000,000이므로 한 칸씩 진행할 수 없습니다. 대신 전이 행렬 T를 만들면,

  • 길이 length만큼 진행한 결과는 T^length 로 표현됩니다.

초기 상태는 아무 문자도 읽지 않은 루트 하나뿐이므로, 초기 벡터에서 T^length를 적용한 뒤 모든 안전 상태 값을 더하면 정답입니다.

5) 시간 복잡도 관점

자동자 상태 수를 S라고 하면,

  • 자동자 구성: 대략 O(전체 패턴 길이)
  • 행렬 거듭제곱: O(S^3 log length)

이 문제의 제한에서는 패턴 수와 길이가 작아서 S도 비교적 작게 유지됩니다. 즉, 길이가 매우 큰 대신 상태 수가 작다는 점을 이용하는 문제입니다.

6) 구현 포인트

  • 중복 패턴이 들어와도 트라이에 그대로 넣으면 됩니다.
  • length = 0이면 빈 문자열 하나만 있으므로 항상 1입니다.
  • 금지 패턴에 "0"과 "1"이 모두 있으면 길이가 1 이상인 모든 문자열이 막힙니다.
  • 모듈러 덧셈과 곱셈을 매 단계 적용해야 합니다.

이 문제는 여러 패턴 검사 + 상태 압축 + 빠른 거듭제곱을 한 번에 묶어야 풀리는 전형적인 hard 문제입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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