문제 개요
문자열 배열 A가 주어졌다고 가정해 보겠습니다. 여기서 한 번의 '이동(move)'이란 문자열 S에서 짝수 인덱스에 있는 두 문자를 서로 교환하거나, 홀수 인덱스에 있는 두 문자를 서로 교환하는 연산을 의미합니다.
두 문자열 S와 T가 '특수 등가(special-equivalent)' 관계라는 것은, 임의의 이동을 원하는 만큼 수행했을 때 S가 T와 완전히 같아질 수 있다는 뜻입니다. 예를 들어 S = "zzxy"와 T = "xyzz"는 특수 등가입니다. 먼저 S[0]과 S[2]를 교환하여 "xzzy"를 만들고, 이어서 S[1]과 S[3]을 교환하면 "xyzz"가 되기 때문입니다.
특수 등가 문자열 그룹의 정의
배열 A에서 특수 등가 문자열 그룹은 다음 두 조건을 만족하는 공집합이 아닌 부분 집합입니다.
- 그룹 내 모든 문자열 쌍은 서로 특수 등가여야 합니다.
- 그룹은 가능한 한 가장 커야 합니다. 즉, 그룹에 속하지 않으면서 그룹의 모든 문자열과 특수 등가인 문자열 S가 존재하지 않아야 합니다.
예를 들어 입력이 ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]라면 출력은 3입니다. 첫 번째 그룹은 ["abcd", "cdab", "cbad"]인데, 이 세 문자열은 서로 쌍별로 특수 등가이며 다른 어떤 문자열도 이들 전부와 특수 등가가 되지 않습니다. 나머지 두 그룹은 각각 ["xyzz", "zzxy"]와 ["zzyx"]입니다.
해결 접근 방법
이 문제의 핵심은 두 문자열이 특수 등가일 필요충분조건이 '짝수 인덱스 문자들을 정렬한 결과와 홀수 인덱스 문자들을 정렬한 결과가 각각 동일'하다는 점입니다. 교환 연산은 같은 패리티(짝수↔짝수, 홀수↔홀수) 인덱스 사이에서만 일어나므로, 문자들이 어느 위치로 이동하더라도 짝수 인덱스 집합과 홀수 인덱스 집합은 서로 섞이지 않습니다.
따라서 다음 단계로 문제를 해결할 수 있습니다.
- 빈 집합(set) codes를 생성합니다.
- A의 각 단어에 대해 다음을 수행합니다.
- 짝수 인덱스 문자들을 정렬한 문자열과 홀수 인덱스 문자들을 정렬한 문자열을 이어 붙여 고유한 코드(code)를 만듭니다.
- 코드를 codes 집합에 추가합니다.
- 최종적으로 codes의 크기를 반환합니다. 집합은 중복을 허용하지 않으므로, 서로 특수 등가인 문자열들은 자연스럽게 하나의 그룹으로 묶입니다.
구현 예제
class Solution: def numSpecialEquivGroups(self, A): codes = set() for word in A: code = ''.join(sorted(word[::2])) + ''.join(sorted(word[1::2])) codes.add(code) return len(codes) ob = Solution() print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","zzyx"]))
입력
["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
출력
3
복잡도 분석
단어의 개수를 N, 각 단어의 길이를 K라고 하면, 매 단어마다 두 번의 정렬(O(K log K))을 수행하므로 시간 복잡도는 O(N × K log K)입니다. 집합에는 최대 N개의 길이 K짜리 코드가 저장되므로 공간 복잡도는 O(N × K)입니다.