[백준] 1305 광고 - KMP(JAVA)

문제링크 🚩

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

1305번: 광고

 

​

📕 문제 접근 📕

- 해당 문제도 KMP 알고리즘을 사용한다(?).

 

- 개인적인 생각으로는 KMP를 위한 table만 설계하면 끝난다고 생각하여 반쪽짜리  KMP 느낌이 든다.

 

포인트 

  1)  광고 문자열은 무한히 반복한다.

 

  2)  무한히 반복하는 문자열 중 일부분만 확인하다.

 

  3)  그광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다.

 

 

문자열에서 접두사 - 접미사가 같은 문자열의 최대 길이를 구한다.

 

 

접두사와 접미사가 같으면 광고 문자열의 같은 시작지점(또는 끝지점) 이 보장된다.

 

 

 

 광고 문자열의 최소 길이는 전체 길이 - 접미사의 최대 길이 가된다 

 

 

 

 

💻 Code 💻

 

package KMP;

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

public class BOJ_1305_광고 {
    private static int makeTable(String str, int N){
        int len = N;
        int[] table = new int[len];
        int cnt = 0;

        int j = 0;

        for (int i = 1; i <len ; i++) {
            while(j > 0 && str.charAt(i) != str.charAt(j)){
                j = table[j-1];
            }
            if(str.charAt(i) == str.charAt(j)){
                table[i] = ++j;

            }
        }

        return table[len -1]; //
    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        System.out.println(N- makeTable(str,N));

    }
}

 

 

📖 배운점 📖

- KMP 알고리즘을 그냥 외워서 사용했다면 습관처럼 KMP 라는 클래스를 제작하여 비교했을 것 같다.

- 문제를 꼼꼼히 읽고 어떤 문제의 요구사항을 먼저 정의하는 것이 필요할 것 같다는 생각이 든다.