[백준][Python] 2195 문자열 복사

그리디, 문자열 / 골드 5

©

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

2195번: 문자열 복사

 

 

내 풀이

S = input()
P = input()
s = 0
e = 1
ans = 0

while len(P) > 0:
    while P[s:e] in S:
        e += 1
        if e > len(P):
            break
    ans += 1
    P = P[e-1:]
    s = 0
    e = 1

print(ans)

 

 

코드 설명

 

s: 시작 인덱스. 0으로 초기화.

e: 끝 인덱스. 1로 초기화. (최소 한 개의 문자를 copy 해야 하므로)

ans: 정답 변수(copy 함수의 최소 사용 횟수)

s = 0
e = 1
ans = 0

 

P가 빈 문자열이 될 때까지 반복문을 실행한다.

while len(P) > 0:

 

P[s:e] 문자열이 S에 있다면 반복문을 실행한다.

➡ 문자열을 하나씩 늘려가며(끝 인덱스(e)를 1씩 증가시키면서) S에 해당 문자열이 있는지 검사하는 과정을 반복한다.

이때, 끝 인덱스(e)가 P의 길이보다 커진다면, 인덱스를 벗어난 것이기 때문에 즉시 종료한다.

 

문자열을 하나씩 늘려가면서 검사하는 이유는!

copy함수의 사용 횟수를 최소화해야 하기 때문이다.

한 번에 최대한 많은 문자열을 copy 해오는 것이 핵심이다.

while P[s:e] in S:
    e += 1
    if e > len(P):
        break

 

반복문 종료 후,

정답 변수(ans)를 1만큼 증가시켜 주고, copy가 완료된 다음 인덱스부터 끝까지의 문자열로 P를 갱신한다.

이제 시작 인덱스(s)와 끝 인덱스(e)를 다시 처음으로 돌려서 검사한다.

ans += 1
P = P[e-1:]
s = 0
e = 1