[백준 1305] 광고 (JAVA)

백준(BOJ) 1305 광고

 

난이도
230101 기준 플래티넘 4

사용 알고리즘
KMP

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

1305번: 광고

 

풀이 과정

 

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

 

 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.

 전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.

 광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.

 예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.

 세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

 

 

입력

 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다.

 

출력

 첫째 줄에 가능한 광고의 길이중 가장 짧은 것의 길이를 출력한다.

 

제한

• 1 ≤ L ≤ 1,000,000
• 광고판에 보이는 문자열은 알파벳 소문자로만 이루어져 있다.

 

 

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

 

 KMP 연습용으로 KMP 알고리즘을 사용하는 문제를 골라서 KMP 알고리즘을 사용할 것인데 이 정보를 모른다고 하더라도 풀이를 구상하다보면 KMP 알고리즘으로 풀어야 할 것이라는 감이 옵니다.

 

 

3. 풀이 구상

 

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

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

 전체 문자열에서 접두사와 접미사가 같은 가장 긴 길이를 전체 문자열 길이에서 빼버리면 되는데요

 pi 배열만 만들면 되고

L - pi[L-1] 가 답이 될 것입니다.

 코드자체는 찾기 문제보다 짧아졌는데 KMP 알고리즘을 사용한다는 것을 모르고 풀었으면 떠올리기 쉽지는 않겠네요

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.*;

public class Main {

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

        int j = 0;

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

        }

        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));

        int L = Integer.parseInt(br.readLine());
        String adv = br.readLine();

        int[] pi = getPi(L,adv);

        bw.write(L-pi[L-1]+"");
        bw.flush();
        bw.close();
        br.close();
    }

}

 

---

풀이 후기

 

코드자체는 찾기 문제보다 짧아졌는데 KMP 알고리즘을 사용한다는 것을 모르고 풀었으면 떠올리기 쉽지는 않겠네요

KMP에 익숙해지기에 시간이 좀 걸릴듯 합니다.