[백준] #2195 문자열 복사(python)

수영·2023년 1월 5일

백준

목록 보기

103/117

📌문제

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

예를 들어 S="abaabba", P="aaabbbabbbaaa"인 경우를 생각해 보자. 이때는 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1) 를 수행하여 P를 만들 수 있다. 각 단계별로 P는 "aa", "aaabb", "aaabbba", …와 같이 변하게 된다.

이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 없는 경우는 입력으로 주어지지 않는다고 가정하자. 각 문자열은 최소한 한 개의 문자로 이루어져 있다.

출력

첫째 줄에 copy 함수의 최소 사용횟수를 출력한다.

예제 입력

xy0z
zzz0yyy0xxx

예제 출력

백준 2195번 문제

💡Idea

문자열 S의 부분 문자열들을 이용하여 문자열 P를 만들어야 하는 문제입니다.

copy 함수를 최소 횟수를 사용하려면, copy 함수를 사용할 때 한 번에 최대한 긴 문자열을 copy해야 합니다.

따라서 문자열 P를 차례대로 살펴보며, 문자열 S에서 그와 동일한 가장 긴 부분 문자열을 찾아주며 문제를 해결해보고자 했습니다.

S에서 P와 동일한 문자를 찾는다.

해당 위치에서 S와 P 모두 하나씩 전진하며 두 문자가 동일한지를 확인한다.

그렇게 가장 긴 동일한 문자를 찾고, 해당 부분까지의 copy 횟수를 1 증가시킨다.

P의 모든 문자들이 확인될 때까지 위의 세 단계를 반복한다.

👩‍🏫 예를 들어, S = abaabba이고, P = aaabbbabbbaaa에서의 copy 함수의 최소 사용횟수를 구해봅시다.

P의 맨 앞의 a 부터 시작해본다고 할 때, S에서는 a를 아래와 같이 찾을 수 있습니다.

0번째 인덱스의 a
2번째 인덱스의 a
3번째 인덱스의 a
6번째 인덱스의 a

0번째 인덱스인 경우, P의 다음 문자인 a와 S의 다음 문자인 b가 일치하지 않기 때문에 가장 길게 일치하는 부분 문자열의 길이는 1입니다.

1번째 인덱스의 경우, P의 다음 문자인 a와 S의 다음 문자인 a가서로 일치하고, 그 다음 문자는 각각 a와 b로 일치하지 않으므로 가장 길게 일치하는 부분 문자열의 길이는 2입니다.

이처럼 3번째와 6번째 인덱스까지 확인을 해보면, 1번째 인덱스의 a부터 시작해서 길이가 2인 부분 문자열 aa를 사용하는 것이 copy의 횟수를 가장 줄일 수 있는 방법입니다.

💻코드

⏰ 시간 : 348 ms / 메모리 : 30616 KB

import sys
input = sys.stdin.readline

S = input().strip()
P = input().strip()
index_p = 0
ans = 0

while index_p < len(P):
    max_value, temp, index_s = 0, 0, 0
    while index_s < len(S) and index_p + temp < len(P):
        if P[index_p + temp] == S[index_s]:
            temp += 1
            max_value = max(max_value, temp)
        else:
            temp = 0
        index_s += 1
    index_p += max_value
    ans += 1
print(ans)