백준 6550 - 부분 문자열 (파이썬)

https://www.acmicpc.net/problem/6550

풀이

문자열 S가 문자열 T의 부분 문자열인지 판별하는 문제이다.

즉, S에 포함된 문자들이 T에서 순서를 유지하면서 존재하는지를 확인 해야 한다.

pos = 0
good = True

pos는 T에서 S의 문자를 찾을 위치를 나타내는 포인터이다.

good은 S가 T의 부분 문자열인지 여부를 저장하는 불 변수이다.

for i in range(len(S)) :
    while pos < len(T) and T[pos] != S[i] :
        pos += 1

S의 문자를 차례대로 순회하면서, T에서 해당 문자를 찾을 때까지 pos를 증가시킨다.

T[pos] == S[i]가 성립할 때까지 pos를 이동한다.

if pos < len(T) :
    pos += 1

T에서 S[i] 문자를 찾으면, 다음 문자를 찾기 위해 pos를 증가시킨다.

else :
    good = False
    break

만약 T에서 끝까지 탐색했는데도, S[i] 문자를 찾지 못하면 good = False로 설정하고 반복문을 종료한다.

시간 복잡도 분석

• while 문을 통해 여러 개의 테스트 케이스를 처리함
• for i in range(len(S))에서 S의 길이만큼 순회함
• 내부에서 while pos < len(T) and T[pos] != S[i]가 실행되지만, T 전체를 한 번만 순회하므로 O(T)
• 따라서 전체 시간 복잡도는 O(S + T) 로 매우 효율

코드

# 백준 6550 - 부분 문자열
# 분류 : 문자열, 그리디
 
while True :
    try :
        S, T = input().split()
 
        pos = 0
        good = True
        for i in range(len(S)) :
            while pos < len(T) and T[pos] != S[i] :
                pos += 1
            
            if pos < len(T) :
                pos += 1
            else :
                good = False
                break
        if good :
            print("yes")
        else :
            print("no")
    except :
        break