[백준] 2195번. 문자열 복사(JAVA)

문제

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

---

풀이(30분)

import java.io.*;

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 nextIdx = 0;
        int count = 0;

        while (nextIdx < p.length()) {
            int maxLength = 0;
            
            // 가능한 가장 긴 부분 문자열을 찾음
            for (int len = 1; nextIdx + len <= p.length(); len++) {
                if (s.contains(p.substring(nextIdx, nextIdx + len))) {
                    maxLength = len; // 현재 가능한 길이 갱신
                } else {
                    break; // 더 이상 늘릴 수 없으면 종료
                }
            }

            nextIdx += maxLength; // 찾은 부분 문자열의 길이만큼 이동
            count++; // 분할 횟수 증가
        }

        System.out.println(count);
    }
}

---

문제 풀이 전략

 

S와 P모두 1000자 이하이기 때문에 직접 탐색하는 것을 목표로 했다.

 

과정은 단순하다.

1.p를 완성해야 하는 기준이 되는 문자를 먼저 선택한다. (처음의 경우 p의 인덱스 0이 된다.)

2. s에서 p의 기준 문자를 만족하는 경우 길이를 계속 늘려가며 최대 몇 개의 문자를 만족하는지 본다.

3. 이 중 가장 긴 것을 빼주고 다시 반복한다.