JS Coding Blog

가장 길게 다시 나타나는 로그 조각

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

today hard rolling-hash 함수명: longestRepeatedLogSnippet 제한 시간: 500ms

길이가 가장 긴 반복 부분 문자열을 찾아 반환하세요. 같은 길이의 후보가 여러 개라면 사전순으로 가장 앞선 문자열을 고르면 됩니다.

문제 설명

문자열 log가 주어집니다.

log 안에서 서로 다른 시작 위치에 두 번 이상 등장하는 부분 문자열 중, 길이가 가장 긴 문자열을 반환하는 longestRepeatedLogSnippet 함수를 작성하세요.

반복 구간은 서로 겹쳐도 인정합니다. 예를 들어 "banana"에서는 "ana"가 인덱스 1과 3에서 겹쳐 등장하므로 유효한 반복 부분 문자열입니다.

가장 긴 반복 부분 문자열이 여러 개라면 사전순으로 가장 앞선 문자열을 반환하세요. 반복되는 부분 문자열이 전혀 없다면 빈 문자열 ""을 반환합니다.

제한사항

  • 1 <= log.length <= 200,000
  • log는 소문자 영문자로만 이루어집니다.
  • 반환값은 조건을 만족하는 문자열입니다.
  • 같은 부분 문자열은 시작 위치가 다르면 여러 번 등장한 것으로 봅니다.
  • 반복 구간은 겹쳐도 됩니다.

예시

  • 입력: "banana" → 출력: "ana"
  • 입력: "abcd" → 출력: ""
  • 입력: "aaaaa" → 출력: "aaaa"
  • 입력: "ababa" → 출력: "aba"

힌트

  • 길이가 L인 반복 부분 문자열이 존재한다면, 그보다 짧은 길이도 항상 존재합니다.
  • 그래서 정답 길이는 이분 탐색으로 찾을 수 있습니다.
  • 어떤 길이 L이 주어졌을 때, 길이 L의 모든 부분 문자열을 빠르게 비교하려면 매번 문자열을 직접 잘라 비교하지 않는 방법이 필요합니다.
  • rolling hash를 사용하면 부분 문자열 하나를 숫자처럼 빠르게 비교할 수 있습니다.

해설

핵심은 정답의 길이를 먼저 찾고, 그 길이 안에서 실제 답 문자열을 고르는 것입니다.

1. 길이에 대한 이분 탐색

어떤 길이 L의 반복 부분 문자열이 존재한다고 합시다. 그러면 그 문자열의 앞 L - 1글자도 당연히 두 번 이상 등장합니다. 즉 반복 부분 문자열의 존재 여부는 길이에 대해 단조성을 가집니다.

  • 길이 L이 가능하면 그보다 짧은 길이도 가능
  • 길이 L이 불가능하면 그보다 긴 길이도 불가능

따라서 1부터 log.length - 1 사이에서 최대 가능한 길이를 이분 탐색할 수 있습니다.

2. 길이 L이 가능한지 빠르게 검사

길이 L의 모든 부분 문자열을 직접 비교하면 너무 느립니다. 문자열 길이가 최대 200,000이므로 O(n^2) 방식은 사용할 수 없습니다.

여기서 rolling hash를 사용합니다.

  • 문자열의 prefix hash를 미리 계산합니다.
  • 그러면 임의의 구간 [i, i + L - 1]의 hash를 O(1)에 구할 수 있습니다.
  • 길이 L의 모든 부분 문자열의 hash를 왼쪽부터 보면서, 같은 hash가 다시 나오면 실제 문자열 후보가 반복된 것입니다.

실전에서는 hash 충돌 가능성을 줄이기 위해

  • BigInt 기반 큰 모듈러를 쓰거나
  • 서로 다른 두 개의 hash를 함께 쓰는 방식 중 하나를 사용하면 안전합니다.

3. 사전순으로 가장 앞선 답 고르기

최장 길이 bestLen을 찾은 뒤에는, 길이 bestLen의 반복 부분 문자열들을 다시 검사하면서 후보를 모읍니다.

  • 두 번 이상 나온 후보만 답 후보입니다.
  • 후보가 여러 개면 문자열 자체를 비교해 사전순 최소를 선택합니다.

이때도 모든 후보를 잘라서 오래 비교하면 느릴 수 있으므로, 먼저 hash로 같은 그룹을 빠르게 찾고, 필요할 때만 실제 substring을 꺼내 비교하는 식으로 구현하면 됩니다.

왜 이 방법이 맞을까?

  • 이분 탐색은 “길이 L이 가능한가?”의 단조성 때문에 가능합니다.
  • rolling hash는 같은 길이 부분 문자열 비교를 빠르게 해 줍니다.
  • 마지막에 최장 길이에서만 사전순 최소를 고르면, 문제의 두 조건인 1) 길이가 최대 2) 동률이면 사전순 최소 를 정확히 만족합니다.

복잡도

  • prefix hash 전처리: O(n)
  • 길이 판정 한 번: O(n)
  • 이분 탐색: O(log n)번
  • 전체: O(n log n)

따라서 큰 문자열도 충분히 처리할 수 있습니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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