[자바] 백준 2195 - 문자열 복사 (boj java)

문제 : boj2195

 

  p의 각 부분 문자열들에 대해 가장 s에 많이 포함되도록 골라주면 된다. 예를들어 예제 입력 1의 경우엔 다음과 같다.

xy0z
zzz0yyy0xxx

 

위의 경우로만 보면 헷갈릴수도 있으니 다음의 예시를 봐보자.

abxyz
abababxyzzz

위와 같이 p를 각 부분문자열로 나눴을 때의 각 부분문자열이 s에 가장 많이 포함되게 해주면 된다.

 

그럼 이 부분문자열 구간을 어떻게 나눌 수 있을까?

간단하게, p의 첫번째 문자부터 차례대로 보면서 s에 포함되어있는 최대 부분문자열까지 잘라내면 된다.

예를들어 위의 예제는 다음과 같이 진행된다.

 

1. abababxyzzz

  "a"는 s에 포함되므로 좀 더 봐보자.

 

2. abababxyzzz

  "ab"도 s에 포함되므로 좀 더 봐보자.

 

3. abababxyzzz -> abababxyzzz

  "aba"는 s에 포함되지 않으므로, 이전에 봤던 "ab"가 최대치이다. 그러니 일단 구간 1개를 확인했고, 현재 위치부터 다시 보자.

 

4. abababxyzzz

5. abababxyzzz -> abababxyzzz

  마찬가지로 구간 하나를 더 찾았고, s에 포함되지 않았던 부분부터 다시 보자.

 

...

 

10. abababxyzzz

11. abababxyzzz -> abababxyzzz

  "abxyzz"는 s에 포함되지 않으므로 직전의 "abxyz"가 또 하나의 구간이다. 포함되지 않는 z 부터 다시 보기 시작하자.

...

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String p = br.readLine();
        int idx = 0;
        int cnt = 0;
        for (int i = 0; i < p.length(); i++) {
            if (s.indexOf(p.substring(idx, i+1)) != -1) continue;
            cnt++;
            idx = i;
        }
        System.out.println(cnt+1);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}