[백준 - 2253][GOLD 5][해설 X] - 문자열 복사 (JAVA)

 

문제 링크

---

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

 

문제

---

어떤 원본 문자열 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 함수의 최소 사용횟수를 출력한다.

 

해결 코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String S = br.readLine();
        String P = br.readLine();

        int count = 0;

        StringBuilder sb = new StringBuilder();

        for(int i=0;i<P.length();i++){
            sb.append(P.charAt(i));

            //현재까지 범위(sb에 들어있는 문자열)의 문자가 S에 포함되어 있지 않다면 이전까지는 포함한다는 의미이기 때문에
            //이전까지 문자열을 copy하고 현재 문자부터 다시 문자열을 만들어 탐색한다.
            if(!S.contains(sb)){
                count++;
                sb.setLength(0);
                sb.append(P.charAt(i));
            }

            //S에 범위의 문자열이 포함된다면 다음에도 포함될 수 있으므로 다음으로 넘긴다.
        }

        count++;    //sb에 남은 문자열을 추가로 더한다.

        System.out.println(count);
    }
}

 

 

실행 결과

---

 

팁

---

• contains의 시간 복잡도는 O(문자열의 길이=N*탐색 대상 문자열의 길이=M)이다.
  • 이때 N과 M이 항상 최악인 경우는 이론상 없기 때문에 평균을 내었을 때 O(N)으로 봐도 무방하다