백준 2195번 <문자열 복사>

백준 알고리즘 2195번

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

2195번: 문자열 복사

---

2195번

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

 

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

---

문제 해결

S와 P의 길이가 1000을 넘지 않기 때문에 그리디와 함께 모두 봄으로써 풀 수 있다.

 

만들어야 하는 문자열 P를 처음부터 만들어 나가는데 가장 길게 만들 수 있는 길이를 찾았다.

만들어야 하는 P의 인덱스를 저장한 idx를 가지고 문자열 S에서 만들 수 있는 길이 중 가장 긴 것을 찾았다. 이를 구현한 것이 getLen(start) 함수이다.

getLen 함수에서 S는 start부터, P는 idx부터 시작해 일치하는 길이를 세서 반환을 해준다. 이때, for문 변수의 끝을 Math.min(S의 길이, P의 길이) 까지로 해주었는데 이는 S와 P가 같은 경우에 제대로 된 값을 반환해주기 위해서이다. 

(for문 안의 if문으로 어차피 범위를 벗어나는 경우를 걸러주기 때문에 가능하다. )

---

코드

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

public class BOJ_2195 {
    static char[] str;
    static int idx;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String origin = br.readLine();
        str = br.readLine().toCharArray();
        idx = 0;
        int cnt = 0;
        while (idx != str.length) {
            check(origin);
            cnt++;
        }
        System.out.println(cnt);
    }
    static void check(String origin){
        int temp = 0;
        for (int i = 0; i < origin.length(); i++) {
            if (origin.charAt(i) == str[idx]) {
                temp = Math.max(getLen(origin, i), temp);
            }
        }
        idx += temp;
    }

    static int getLen(String origin, int start) {
        for (int i = 0; i <= Math.min(origin.length(), str.length); i++) {
            if (start + i == origin.length() || idx + i == str.length) {
                return i;
            }
            if (origin.charAt(start + i) != str[idx + i]) {
                return i;
            }
        }
        return 1;
    }
}

---

결과

---

abcabz
abcabcabaabcab
4


abcabzc
abcabcabzcabcab
3

abcabcabzcabcab
abcabzc
1

abcabcabzcabcab
abcabzzc
2

ab
ab
1

a
aa
2