문제 풀이
그리디
P의 앞에서부터 S의 부분 문자열중 일치하는 가장 긴 부분 문자열을 복사하면 복사 횟수가 최소가 됨
p = P에서 복사해야하는 부분 문자열의 시작 인덱스
t = S의 i번째 인덱스부터 복사를 하면 P의 t번째 인덱스 전까지 복사가 가능함
answer = 복사 최소 횟수
i를 0부터 S의 길이 미만까지 반복하면서 S[i]가 P[p]와 같다면 S의 i번째 인덱스부터 P로 복사하면 다음 복사를 시작해야 하는 인덱스 t를 구해 S의 부분 문자열을 복사할 때 최대 인덱스를 max로 구하고 나서 p에 max를 대입하고 answer 값 증가
이를 p가 P의 길이가 될때까지 반복하면 복사의 최소 횟수가 저장되므로 이를 출력하면 정답
풀이 설명
어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.
이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.
S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.
copy 함수를 최소로 사용해 P를 만드려면 한 번 copy를 사용할 때 최대한 긴 부분 문자열을 복사하면 된다. P의 맨 앞에서부터 부분 문자열을 자르면 이 부분 문자열이 한 번 copy를 사용할 때 복사되는 부분 문자열이므로 이 부분 문자열이 최대한 길어야 copy의 사용 횟수를 줄일 수 있다.
따라서 P의 맨 앞에서부터 부분 문자열을 잘랐을 때 S의 부분 문자열과 일치하고 가장 긴 부분 문자열인지를 찾으면 된다. 이를 찾기 위해서 copy를 사용했을 때 P로 복사되는 부분 문자열의 시작 인덱스를 p로 정의하고 0으로 초기화한다.
P의 p에서 시작하는 부분 문자열과 일치하는 가장 긴 S의 부분 문자열을 구하기 위해 i를 0부터 S.length 미만까지 반복하며 i부터 시작하는 S의 부분 문자열이 일치하는지 확인하기 위해 P[p]와 S[i]를 비교한다.
같다면 i부터 시작하는 부분 문자열이 어디까지 일치하는지 확인하기 위해 임시 변수 t를 만들고 p를 대입하고 임시 변수 s를 만들고 i를 대입하고 S[s]와 P[t]가 일치하는 동안 s와 t를 증가시킨다. 그러면 i부터 시작하는 S의 부분 문자열이 p부터 시작하고 t의 전에서 끝나는 부분 문자열과 일치하는 것이므로 복사를 한다면 다음으로 확인해야 하는 P의 문자열이 t에서부터 확인해야 하므로 이 때의 t의 최댓값을 저장하기 위해 max와 비교해 최댓값을 저장한다.
이를 모든 i에 대해 확인하면 현재 최대 길이로 복사를 하면 다음 부분 문자열을 max부터 확인해야 하므로 answer를 증가시켜 복사했다는 것을 나타내고 p에 max를 대입해 다음 부분 문자열을 확인한다.
이를 p가 P.length가 될때까지 반복하면 최소 복사 횟수가 answer에 저장되므로 이를 출력하면 정답이 된다.
소스 코드
fun main(){
val br = System.`in`.bufferedReader()
val S = br.readLine()
val P = br.readLine()
var p = 0
var answer = 0
while(p < P.length){
var max = p
for(i in 0 until S.length){
if(S[i] == P[p]){
var s = i
var t = p
while(s < S.length && t < P.length && S[s] == P[t]){
s++
t++
}
max = maxOf(max, t)
}
}
answer++
p = max
}
println(answer)
}