문자열의 회전 그룹(rotation group)이란 해당 문자열이 가질 수 있는 모든 고유한 회전 형태를 모아 놓은 집합을 의미합니다. 예를 들어 입력이 "567"이라면, 이 문자열은 "675"와 "756"으로 회전할 수 있으며, 이 세 문자열은 모두 같은 회전 그룹에 속하게 됩니다.
이제 문자열 목록 words가 주어졌을 때, 각 단어를 회전 그룹별로 묶고 총 그룹의 개수를 구하는 것이 목표입니다.
예를 들어 입력이 다음과 같다면,
words = ["xyz", "ab", "ba", "c", "yzx"]
출력은 3이 됩니다. 회전 그룹이 정확히 세 개 존재하기 때문입니다.
- ["xyz", "yzx"]
- ["ab", "ba"]
- ["c"]
해결 접근 방법
이 문제는 집합(set)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 회전 결과를 저장할 새로운 집합
s를 생성하고, 그룹 개수를 세는 변수ct를 0으로 초기화합니다. words의 각 단어i에 대해 다음을 반복합니다.- 만약
i가 아직 집합s에 없다면, 이것은 새로운 회전 그룹이라는 의미이므로ct를 1 증가시킵니다. j를 0부터 단어 길이까지 반복하면서, 인덱스j부터 끝까지의 부분 문자열과 처음부터j까지의 부분 문자열을 이어 붙인 값을 만들어 집합s에 추가합니다.
- 만약
- 모든 단어를 처리한 후 최종적으로
ct를 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
class Solution: def solve(self, words): s=set() ct=0 for i in words: if i not in s: ct+=1 for j in range(len(i)): s.add(i[j:]+i[:j]) return ct ob = Solution() print(ob.solve(["xyz", "ab", "ba", "c", "yzx"]))
입력
["xyz", "ab", "ba", "c", "yzx"]
출력
3
동작 원리 설명
첫 번째 단어 "xyz"는 집합에 없으므로 카운트가 1이 되고, "xyz", "yzx", "zxy"가 집합에 추가됩니다. 두 번째 단어 "ab" 역시 집합에 없으므로 카운트가 2가 되고, "ab"와 "ba"가 추가됩니다. 세 번째 단어 "ba"는 이미 집합에 있으므로 카운트가 증가하지 않습니다. 네 번째 단어 "c"는 새로운 단어이므로 카운트가 3이 됩니다. 마지막 단어 "yzx"는 이미 "xyz"의 회전 형태로 집합에 존재하기 때문에 카운트가 늘어나지 않습니다. 따라서 최종 결과는 3이 반환됩니다.
이 방법의 시간 복잡도는 각 단어의 길이를 L, 단어 개수를 N이라 할 때 대략 O(N × L²)이며, 공간 복잡도는 저장되는 회전 문자열의 수에 비례하여 O(N × L²)입니다.