문제 개요
소문자 알파벳으로 구성된 문자열 s와 '쌍(pairs)'이라는 리스트가 있다고 가정해 보겠습니다. pairs의 각 요소는 [a, b] 형태의 두 문자로 이루어져 있으며, 여기서 문자 a와 b는 서로 동일하다고 간주됩니다.
만약 [a, b]와 [b, c]라는 두 쌍이 존재한다면, a와 b가 동등하고 b와 c도 동등하므로, 추이성에 의해 a와 c 역시 동등하다고 볼 수 있습니다. 또한 모든 값은 자기 자신과 항상 동등합니다. 이러한 동등 관계를 바탕으로 문자열 s가 회문(palindrome)인지 판별하는 것이 목표입니다.
예시
입력이 s = "raceckt", pairs = [["r", "t"], ["a", "k"], ["z", "x"]]라고 해보겠습니다. 이때 "a" = "k"이고 "r" = "t"이므로, 해당 문자열은 "racecar"로 치환될 수 있으며 이는 회문입니다. 따라서 출력은 True가 됩니다.
접근 방법
이 문제는 그래프 탐색 기법(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 각 쌍을 그래프의 간선으로 보면, 동등한 문자들이 하나의 연결 요소(동등 클래스)를 이루게 됩니다. 풀이 절차는 다음과 같습니다.
- g: 중복을 허용하는 그래프의 인접 리스트를 생성합니다.
- G: 중복을 허용하지 않는 그래프의 인접 리스트(집합)를 생성합니다.
- pairs의 각 (x, y)에 대해 다음을 수행합니다:
- g[x] 끝에 x를 추가
- g[y] 끝에 y를 추가
- g[x] 끝에 y를 추가
- g[y] 끝에 x를 추가
- pairs의 각 (x, y)에 대해 다음을 수행합니다:
- dfs() 함수를 정의합니다. 이 함수는 a와 so_far를 인자로 받습니다.
- a를 so_far에 추가합니다.
- g[a]의 각 원소 elem에 대해, elem이 so_far에 없다면 dfs(elem, so_far)를 재귀 호출합니다.
- 메인 로직에서 다음을 수행합니다:
- g의 각 키(key)에 대해 dfs(key, G[key])를 호출하여 동등 클래스를 완성합니다.
- i를 0부터 len(s)//2 - 1까지 반복하면서 다음을 검사합니다:
- s[i] == s[len(s)-1-i]이거나, s[i]가 G[s[len(s)-1-i]]에 속하거나, s[len(s)-1-i]가 G[s[i]]에 속한다면 → 다음 반복으로 진행
- 그렇지 않다면 → False 반환
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 전체 구현 과정을 확인할 수 있습니다.
from collections import defaultdict
def solve(s, pairs):
g = defaultdict(list)
G = defaultdict(set)
for x, y in pairs:
g[x].append(x)
g[y].append(y)
g[x].append(y)
g[y].append(x)
def dfs(a, so_far):
so_far.add(a)
for elem in g[a]:
if elem not in so_far:
dfs(elem, so_far)
for key in g:
dfs(key, G[key])
for i in range(0, len(s) // 2):
if s[i] == s[-1 - i] or (s[i] in G[s[-1 - i]] or s[-1 - i] in G[s[i]]):
continue
else:
return False
return True
s = "raceckt"
pairs = [["r", "t"], ["a", "k"], ["z", "x"]]
print(solve(s, pairs))
입력
"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]
출력
True
정리
이 알고리즘은 동등 관계를 그래프의 연결 요소로 모델링한 뒤, DFS를 통해 각 문자가 속한 동등 클래스를 미리 계산합니다. 이후 문자열의 양 끝에서부터 중앙으로 이동하며 대칭 위치의 문자들이 직접 일치하거나 동등한지만 확인하면 됩니다. 시간 복잡도는 그래프 구축 및 탐색에 O(P + α), 회문 검사에 O(N/2)로, 전체적으로 매우 효율적입니다.