문제 개요
문자열 s와 패턴 역할을 하는 문자열 t가 주어졌을 때, s의 문자들이 t에 나타난 순서를 그대로 따르는지 확인하는 문제입니다. 이때 패턴 t에는 중복된 문자가 없다고 가정합니다.
예를 들어 s = 'hello world', t = 'hw'라고 해봅시다. 'h'가 'w'보다 먼저 등장하므로 결과는 True입니다.
풀이 접근 방법
핵심 아이디어는 패턴의 인접한 두 문자 쌍(x, y)에 대해, 문자열 s 안에서 x의 마지막 등장 위치가 항상 y의 첫 등장 위치보다 앞서 있거나 같은지 검사하는 것입니다. 모든 인접 쌍이 이 조건을 만족하면 s는 패턴의 순서를 따른다고 결론지을 수 있습니다.
알고리즘 단계
- s의 길이가 t의 길이보다 작으면 False를 반환합니다.
- i를 0부터 len(t) - 2까지 반복하면서 다음을 수행합니다.
- x := t[i], y := t[i + 1]
- right := x가 s에서 마지막으로 등장하는 인덱스
- left := y가 s에서 처음으로 등장하는 인덱스
- right가 -1이거나 left가 -1이거나 right > left이면 False를 반환합니다.
- 모든 반복을 통과하면 True를 반환합니다.
right나 left가 -1이라는 것은 해당 문자가 s에 아예 존재하지 않는다는 뜻이므로 순서를 확인할 수 없어 False가 됩니다. 또한 right > left인 경우는 x가 y보다 늦게 등장하는 경우가 존재한다는 의미이므로 역시 False입니다.
파이썬 구현 예제
def solve(s, t):
if len(s) < len(t):
return False
for i in range(len(t) - 1):
x = t[i]
y = t[i + 1]
# x의 마지막 등장 위치와 y의 첫 등장 위치 비교
right = s.rfind(x)
left = s.find(y)
if right == -1 or left == -1 or right > left:
return False
return True
s = 'hello world'
t = 'hw'
print(solve(s, t))참고: str.index()와 str.rindex()는 찾는 값이 없을 때 -1을 반환하지 않고 ValueError 예외를 발생시킵니다. 값이 없을 때 -1을 받아 조건 분기에 활용하려면 위 코드처럼 str.find()와 str.rfind()를 사용하는 것이 안전합니다.
실행 결과
입력:
'hello world', 'hw'
출력:
True
반대로 t = 'wh'처럼 순서가 어긋난 패턴을 입력하면, 'w'의 마지막 등장 위치(인덱스 6)가 'h'의 첫 등장 위치(인덱스 0)보다 뒤에 있으므로 False가 출력됩니다.
복잡도 분석
- 시간 복잡도: O(m × n) — m은 패턴 t의 길이, n은 문자열 s의 길이입니다. 인접 문자 쌍마다 find와 rfind 탐색을 수행하기 때문입니다.
- 공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.