백준 6550번 - 부분 문자열 (Python)
문제 요약
두 문자열 s와 t가 주어졌을 때, s가 t의 부분 문자열(subsequence)인지 판단하는 문제다.
여기서 "부분 문자열"이란, t에서 몇 개의 문자를 제거하고 순서를 바꾸지 않고 합쳤을 때 s가 되는 경우를 말한다. 입력은 여러 테스트 케이스로 이루어져 있고, EOF까지 반복해서 읽어야 한다.
풀이 접근
핵심 아이디어는 간단하다. s의 각 문자를 순서대로 t에서 찾되, 이전에 매칭된 위치 이후부터 탐색하는 것이다. s의 모든 문자를 순서대로 t 안에서 찾을 수 있다면 Yes, 하나라도 못 찾으면 No를 출력한다.
내 코드에서는 매칭에 성공할 때마다 t = t[j+1:]로 t를 슬라이싱해서, 다음 탐색의 시작 위치를 자연스럽게 앞으로 밀어주는 방식을 사용했다.
시간 복잡도
s의 길이를 N, t의 길이를 M이라 하자.
외부 반복문은 s의 각 문자에 대해 최대 N번, 내부 반복문은 t를 순회하면서 매칭을 찾는다. 매칭에 성공하면 t를 슬라이싱하므로 이후 탐색 범위가 줄어든다. 결국 t의 각 문자는 전체 과정에서 최대 한 번만 비교되기 때문에 비교 자체의 총 횟수는 O(M)이다.
다만, t = t[j+1:] 슬라이싱이 매번 새로운 문자열을 생성하므로 이 부분에서 추가 비용이 발생한다. 슬라이싱은 남은 t의 길이만큼 복사하므로, 최악의 경우 총 슬라이싱 비용은 O(M × N)까지 갈 수 있다. (예: s의 모든 문자가 t앞쪽에 몰려 있는 경우)
문제 제한이 s, t 길이 모두 10만 이하이므로 통과에는 문제없지만, 만약 효율을 극대화하고 싶다면 슬라이싱 대신 인덱스 변수(투 포인터)를 사용하는 것이 더 깔끔하다.
로직 순서별 해설
1. 입력 처리 및 EOF 대응
while True:
try:
s, t = sys.stdin.readline().split()
테스트 케이스 수가 정해져 있지 않으므로 while True로 무한 루프를 돌리고, try-except로 EOF를 잡아 종료한다. sys.stdin.readline()을 쓴 이유는 input()보다 입력 속도가 빠르기 때문이다.
2. s의 각 문자를 t에서 순서대로 탐색
check_1 = False
for i in range(len(s)):
check_2 = False
for j in range(len(t)):
if s[i] == t[j]:
t = t[j+1:]
check_2 = True
break
s[i]를 현재 t에서 앞에서부터 찾는다. 찾으면 t를 해당 위치 다음부터 잘라서 갱신하고, check_2 = True로 매칭 성공을 표시한 뒤 내부 루프를 탈출한다.
슬라이싱 t = t[j+1:]이 핵심인데, 이렇게 하면 다음 s[i+1]을 탐색할 때 이미 사용한 부분은 자연스럽게 제외된다.
3. 매칭 실패 시 즉시 No 출력
if check_2 == False:
print("No")
check_1 = True
break
t 전체를 다 돌았는데도 s[i]와 일치하는 문자가 없으면 check_2가 False인 채로 남는다. 이 경우 s는 t의 부분 문자열이 될 수 없으므로 No를 출력하고 외부 루프도 탈출한다.
4. 모든 문자 매칭 성공 시 Yes 출력
if check_1 == False:
print("Yes")
외부 루프가 break 없이 정상 종료됐다면 check_1은 여전히 False다. 이는 s의 모든 문자가 t에서 순서대로 매칭됐다는 뜻이므로 Yes를 출력한다.
5. 예외 처리로 종료
except:
break
입력이 끝나면 readline()이 빈 문자열을 반환하고, .split()이 빈 리스트를 반환해서 언패킹에서 ValueError가 발생한다. 이걸 except로 잡아서 루프를 종료한다.
전체 코드
import os, sys
while True:
try:
s, t = sys.stdin.readline().split()
check_1 = False
for i in range(len(s)):
check_2 = False
for j in range(len(t)):
if s[i] == t[j]:
t = t[j+1:]
check_2 = True
break
if check_2 == False:
print("No")
check_1 = True
break
if check_1 == False:
print("Yes")
except:
break