[백준/6550] 부분 문자열 | 반복문으로 고정된 인덱스 다루기

알고리즘

있는지 없는지 확인하면 되겠네~~ 개꿀~~ 이런 태도로 문제를 대했지만 내가 간과한 것이 있었다.

처음에 이중 for문으로 s랑 t를 비교해서 다르면 pop하는 알고리즘을 생각했는데

이렇게 하면 s가 t의 '부분 문자열'인지 알 수 없다.

왜냐면,, 전체를 돌면서 문자가 다르기만 하면 pop을 해버리니까 '부분 문자열'인지 판단이 불가능하다.

s에 속하는 문자가 있냐/없냐의 문제가 아니라 s가 t의 부분 문자열인가?라는 문제기 때문에 이중 for문으로 s와 t를 도는 식으로는 해결이 불가능하다는 뜻.

 

따라서 s를 단순히 반복하며 t에 있는 문자들과 비교하는 방식이 아니라 순차적으로 돌면서 t에 속하는 문자와 같은지 확인해주면 된다.

 

1. for문으로 비교하고자 하는 t를 돌면서 만약 t의 문자와 같으면 s에 속하는 문자를 가르키는 인덱스를 증가해준다.

2. 인덱스 번호가 s의 모든 문자를 다 돌면 t에 s의 문자들이 속해있다는 것이기 때문에, 부분 문자열이 된다.

최종 코드

while True : 
    try : 
        s, t = input().split()
    except EOFError : break
    idx = 0
    flag = False
    for i in t : 
        if i == s[idx] :
            idx += 1 
            # t == s
            if idx == len(s) : flag = True; break
    print('Yes') if flag else print('No')