[백준] 6550 부분문자열 (Python)

🔗 문제 링크

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

문제

2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

출력

입력된 s와 t의 순서대로 s가 t의 부분 문자열인 경우 Yes라 출력하고 아닐 경우 No라고 출력한다.

예제 입력 1

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

예제 출력 1

Yes
No
Yes
No

✔풀이

import sys 
input = sys.stdin


def solve(s,t):
    idx = 0

    for i in t:
        if idx < len(s) and i == s[idx]:
            idx += 1
    return idx == len(s)

for line in sys.stdin:
    s,t = line.split()

    if solve(s,t):
        print('Yes')
    else:
        print("No")
    

풀이 설명

t를 앞에서부터 한 글자씩 순회하면서, s의 현재 위치(idx) 문자와 같으면 바로 매칭시키고 idx를 올린다. 가장 먼저 만나는 문자를 즉시 취하는 그리디 방식이다.

t를 다 돌았을 때 idx == len(s)이면 s의 모든 문자를 순서대로 찾은 것이다.

s = "abcc", t = "absdacadssdc" 로 따라가보면:

idx = 4 == len("abcc") → Yes ✓

왜 그리디가 성립할까?

s의 i번째 문자를 t에서 최대한 빨리 매칭시키는 게 항상 최적이다. 일찍 매칭할수록 뒤에 남은 t의 공간이 넓어져서, 나머지 문자를 찾을 기회가 줄어들지 않기 때문이다.

시간복잡도

O(|t|) — t를 한 번만 순회하면 끝난다.