사전순으로 가장 작은 문자열 회전
자바스크립트 코딩테스트 문제로 booth-algorithm 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문자열을 원형으로 회전했을 때 만들 수 있는 문자열 중 사전순으로 가장 작은 문자열을 찾아보세요.
문제 설명
문자열 s가 주어집니다.
문자열의 회전이란 앞쪽 일부 문자를 떼어 뒤에 붙이는 것을 말합니다. 예를 들어 "baca"의 회전 문자열은 "baca", "acab", "caba", "abac"입니다.
이 중 사전순으로 가장 작은 회전 문자열을 반환하는 lexicographicallySmallestRotation 함수를 작성하세요.
제한사항
1 <= s.length <= 200000s는 영문 소문자로만 이루어져 있습니다.- 반환값은
s와 길이가 같은 문자열입니다. - 같은 최소 회전 문자열이 여러 시작점에서 만들어질 수 있어도 반환 문자열은 같습니다.
예시
- 입력:
s = "baca"-> 출력:"abac" - 입력:
s = "dcba"-> 출력:"adcb" - 입력:
s = "abab"-> 출력:"abab" - 입력:
s = "aaaa"-> 출력:"aaaa" - 입력:
s = "banana"-> 출력:"abanan"
힌트
- 모든 회전을 직접 만들어 정렬하면 문자열 길이가 클 때 너무 느립니다.
- 두 시작 후보를 두고 같은 거리의 문자를 비교해 보세요.
- 어떤 위치의 문자가 더 크다는 사실을 알면, 그 후보에서 이어지는 일부 시작점들도 한꺼번에 버릴 수 있습니다.
해설
가장 단순한 방법은 s의 모든 회전 문자열을 만든 뒤 가장 작은 값을 고르는 것입니다. 하지만 길이가 n인 회전 문자열을 n개 만들면 문자열 비교까지 포함해 O(n^2)에 가까워져 제한을 감당하기 어렵습니다.
이 문제는 Booth 알고리즘으로 풀 수 있습니다. 핵심은 사전순 최소 회전의 시작점 후보를 두 개만 유지하면서, 비교 결과로 절대 답이 될 수 없는 시작점 구간을 한 번에 건너뛰는 것입니다.
문자열을 실제로 두 배로 만들 필요는 없지만, 인덱스를 볼 때는 s[(index) % n]처럼 접근해 원형 문자열처럼 비교합니다.
두 후보 시작점을 i, j라고 두고, 두 회전이 현재까지 k글자만큼 같았다고 합시다.
s[(i + k) % n]와s[(j + k) % n]가 같으면k를 늘려 다음 문자를 비교합니다.- 왼쪽 문자가 더 크면
i에서 시작하는 회전이 더 나쁩니다. 이때i부터i + k까지의 시작점도 최소가 될 수 없으므로i = i + k + 1로 건너뜁니다. - 오른쪽 문자가 더 크면 같은 방식으로
j = j + k + 1로 건너뜁니다. - 두 후보가 같아지면 한 칸 더 밀어 서로 다른 시작점을 유지합니다.
이 과정을 두 후보가 모두 문자열 길이 안에 있는 동안 반복하면, Math.min(i, j)가 사전순 최소 회전의 시작점입니다.
예를 들어 "baca"에서는 "b"로 시작하는 회전보다 "a"로 시작하는 후보가 더 좋다는 비교가 일어나고, 이후 "acab"과 "abac"을 비교하면서 "abac"이 더 작다는 사실을 찾아냅니다.
반복 패턴도 주의해야 합니다. "abab"처럼 최소 회전 문자열이 여러 시작점에서 만들어질 수 있는 경우가 있습니다. Booth 알고리즘은 그중 한 최소 시작점을 찾고, 해당 위치에서 길이 n만큼 잘라 반환하면 항상 올바른 최소 회전 문자열이 됩니다.
각 시작점은 후보에서 탈락할 때 앞으로만 이동하므로 전체 비교 횟수는 선형으로 제한됩니다. 시간 복잡도는 O(n), 추가 공간 복잡도는 결과 문자열을 제외하면 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.