2195번 - 문자열 복사

문제 링크

문제 풀이 시간 : 20분

문제 요약

• 원본 문자열 S가 주어진다.
• copy(s, p) 연산은
• 목표는 S를 이용해 문자열 P를 만드는 것
• 단, copy 함수 사용 횟수를 최소화해야 한다.

문제 풀이

이 문제를 보자마자 문자열 메서드를 활용하면 충분히 해결할 수 있겠다고 생각했다.

처음에는 contains()를 사용하려 했지만,

문제는 특정 위치에서 시작하는 부분 문자열이 존재하는지 확인하는 것이기 때문에

indexOf()를 사용하는 것이 더 적절하다고 판단했다.

접근 아이디어

핵심은 매우 단순하다.

P를 왼쪽부터 보면서

그리고:

• 더 이상 늘릴 수 없을 때
• 그 직전까지의 문자열을 한 번에 copy 한다고 생각하고
• copy 횟수를 1 증가
• 그 다음 위치로 이동

이 과정을 P가 끝날 때까지 반복하면 된다.

왜 이 방법이 최소가 되는가?

한 번 copy를 할 때 최대한 길게 복사하는 것이 항상 이득이다.

• 짧게 여러 번 복사하는 것보다
• 가능한 한 가장 긴 문자열을 한 번에 복사하는 것이

즉, 이 문제는 그리디로 해결 가능하다.

알고리즘 흐름

1. si를 0으로 시작
2. P[si...]에서 시작하는 부분 문자열을 하나씩 늘려가며
3. 더 이상 확장할 수 없으면
4. si가 P의 끝에 도달할 때까지 반복

시간 복잡도

• P의 길이 ≤ 1000
• S의 길이 ≤ 1000

각 위치마다 최대 길이만큼 탐색하므로

충분히 시간 제한 내에서 해결 가능하다.

최종 코드

package samsung01;

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String S = br.readLine();
		String P = br.readLine();
		
		int si = 0;
		int ans = 0;
		
		while(si<P.length()) {
			int maxLen = 0;
			for(int i = si+1;i<=P.length();i++) {
				if(S.indexOf(P.substring(si,i)) == -1) {
					break;
				}
				maxLen++;
			}
			si = si+maxLen;
			ans++;
		}
		
		System.out.println(ans);
	}
}