문제 개요
소문자로만 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 우리가 찾아야 할 것은, 문자열 내 서로 다른 위치에 존재하는 또 다른 부분 문자열과 아나그램(anagram) 관계에 있는 모든 부분 문자열입니다. 최종 결과는 사전순(lexicographic order)으로 정렬된 리스트 형태로 반환해야 합니다.
예를 들어 입력이 s = "abcba"라면 출력은 다음과 같습니다.
['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']
위 결과의 각 부분 문자열은 원본 문자열 자체 안에서 서로 다른 위치에 아나그램 짝을 가지고 있습니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 담을 새로운 리스트
res를 생성합니다. L:= 문자열s의 길이i를 1부터 L까지 반복합니다.smap:= 값이 리스트 타입인 빈 딕셔너리(defaultdict)j를 0부터 L-i까지 반복합니다.cs:= 인덱스 j부터 j+i-1까지의 부분 문자열k:=cs를 정렬한 뒤 이어 붙인 문자열 (아나그램 판별용 키)smap[k]의 끝에cs를 추가합니다.
smap의 각 키k와 값v에 대해:v의 크기가 2 이상이면,v의 요소들을res에 삽입합니다.
res를 정렬한 후 반환합니다.
동작 원리
이 알고리즘의 핵심 아이디어는 “문자를 정렬했을 때 결과가 같은 문자열끼리는 서로 아나그램 관계”라는 점입니다. 길이가 i인 모든 부분 문자열을 추출한 뒤, 각 부분 문자열을 정렬한 형태를 딕셔너리의 키로 사용하면 동일한 키를 공유하는 부분 문자열들이 자연스럽게 그룹화됩니다. 특정 그룹에 두 개 이상의 부분 문자열이 존재한다면, 그것들은 서로 다른 위치에서 등장한 아나그램이라는 의미이므로 결과 리스트에 포함하면 됩니다.
예제 코드
다음 파이썬 구현 예시를 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
def solve(s):
res = []
L = len(s)
for i in range(1, L + 1):
smap = defaultdict(list)
for j in range(L - i + 1):
cs = s[j : j + i]
k = "".join(sorted(cs))
smap[k].append(cs)
for k, v in smap.items():
if len(v) >= 2:
res.extend(v)
return sorted(res)
s = "abcba"
print(solve(s))
입력
"abcba"
출력
['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']
마무리
이 방식은 모든 가능한 길이의 부분 문자열을 한 번씩만 순회하면서 해싱 기반 그룹화로 아나그램을 판별하기 때문에 직관적이고 구현이 간단합니다. 다만 부분 문자열 개수가 O(L²)에 비례하고 각각 정렬 연산이 필요하므로, 문자열이 매우 길어질 경우 시간 복잡도가 커질 수 있다는 점은 유의해야 합니다.