[백준 1701] Cubeditor (JAVA)

백준(BOJ) 1701 Cubeditor

 

난이도
230102 기준 골드 3

사용 알고리즘
KMP

문제 링크
https://www.acmicpc.net/problem/1701

1701번: Cubeditor

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

 텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

 

입력

 첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

 

출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 KMP의 pi 배열 구하는 것을 이용하면 풀릴것 같습니다. 문자열의 길이가 최대 5000 이므로 KMP를 사용해야 O(N^2)의 시간복잡도로 시간초과에도 걸리지 않을 것 입니다.

 

3. 풀이 구상

 

 KMP 알고리즘의 pi 배열을 만드는 것을 활용하면 문제를 풀 수 있습니다.

참고 : KMP : 문자열 검색 알고리즘 - 멍멍멍 (tistory.com)

 이 문제는 pi 배열을 만들때 비교하는 문자열을 앞에서부터 한글자씩 줄여가면서 비교하면 됩니다.

 

 

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.*;

public class Main {

    static int resultMax = 0;

    public static int[] getPi(int L, String comp){
        int[] pi = new int[L];

        int j = 0;

        for(int i = 1; i < L; i++){
            while(j>0 && comp.charAt(i)!=comp.charAt(j)){
                j = pi[j-1];
            }
            if(comp.charAt(i)==comp.charAt(j)){
                pi[i] = ++j;
                resultMax = Math.max(resultMax,pi[i]);
            }

        }

        return pi;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String adv = br.readLine();
        int L = adv.length();

        for(int i = 0; i < L ; i++){
            String comp = adv.substring(i);
            int[] pi = getPi(comp.length(),comp);
        }

        bw.write(resultMax+"");
        bw.flush();
        bw.close();
        br.close();
    }

}

 

 

---

풀이 후기

 

 KMP로 푸는 단순한 문제였습니다