[ BOJ ][JAVA][2195] 문자열 복사

www.acmicpc.net/problem/2195

2195번: 문자열 복사

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	177	87	65	45.775%

문제

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

예제 입력 1

xy0z
zzz0yyy0xxx

예제 출력 1

10

코드

/*
    문자열 복사
    그리디, 구현
*/
import java.io.*;
import java.util.*;
public class p2195 {
    static char[] str1, str2;
    static int len1, len2;
    static Map<Character, List<Integer>> map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new HashMap<>();

        str1 = br.readLine().toCharArray();
        len1 = str1.length;
        for (int i = 0; i < len1; i++) {
            char c = str1[i];

            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<>());
            }
            // char가 나타나는 인덱스를 저장
            List<Integer> list = map.get(c);
            list.add(i);
            map.put(c, list);
        }

        str2 = br.readLine().toCharArray();
        len2 = str2.length;

        int i = 0, ans = 0;
        while (i < len2) {
            List<Integer> list = map.get(str2[i]);
            // c가 나오는 index를 하나씩 탐색
            int ret = 0;
            for (int idx : list) {
                int cnt = 0;
                int j = i;
                while (j < len2 && idx < len1) {
                    if (str2[j] == str1[idx]) {
                        j++;
                        idx++;
                        cnt++;
                        continue;
                    }
                    break;
                }
                ret = Math.max(ret, cnt);
            }
            i += ret;
            ans++;
        }

        System.out.println(ans);
    }
}