10월 23일 - 광고

문제
세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.
전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.
광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.
예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.
세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

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

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

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

• 예제 입력 1
  5
  aaaaa
• 예제 출력 1
  1

내 풀이

import java.util.Scanner;

public class Main {

    // KMP 알고리즘에서 패턴에 대한 테이블 생성
    public static int[] createKMPTable(String pattern) {
        int n = pattern.length();
        int[] table = new int[n];
        int j = 0;

        for (int i = 1; i < n; i++) {
            // 패턴이 일치하지 않으면 이전 패턴의 일치 부분으로 돌아간다.
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = table[j - 1];
            }

            // 패턴이 일치하면 테이블에 그 길이를 기록
            if (pattern.charAt(i) == pattern.charAt(j)) {
                table[i] = ++j;
            }
        }

        return table;
    }

    public static int findShortestAdLength(int L, String adString) {
        // KMP 테이블을 통해 반복되는 패턴 길이를 찾아낸다.
        int[] kmpTable = createKMPTable(adString);
        // L에서 가장 긴 접미사/접두사 일치 길이를 뺀 것이 반복을 제외한 실제 광고 길이
        return L - kmpTable[L - 1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        int L = sc.nextInt();
        String adString = sc.next();

        // 결과 계산
        int shortestLength = findShortestAdLength(L, adString);

        // 결과 출력
        System.out.println(shortestLength);

        sc.close();
    }
}

코드 설명:

createKMPTable 함수:

• 패턴을 분석하여 KMP 알고리즘의 테이블을 만드는 함수입니다. 이 테이블은 접두사와 접미사가 일치하는 부분을 효율적으로 계산해주는 역할을 합니다.

findShortestAdLength 함수:

• KMP 테이블을 기반으로 전체 광고 길이에서 중복되는 부분을 제외한 가장 짧은 광고 길이를 찾는 함수입니다.

메인 함수 (main):

• 입력을 처리하고, findShortestAdLength 함수로 결과를 계산한 후 출력합니다.

KMP 알고리즘을 사용한 이유

• 문자열 내에서 반복되는 패턴을 찾기 위한 효율적인 방법으로 KMP 알고리즘을 사용했다.

• KMP 알고리즘은 접두사와 접미사가 일치하는 부분을 재활용함으로써 불필요한 비교를 줄여준다. 이를 통해 시간 복잡도가 O(n)으로, 전체 문자열을 빠르게 분석할 수 있다.

주요 배운 점

• KMP 알고리즘의 LPS 테이블을 생성하는 과정을 다시 이해할 수 있었다. 문자열에서 반복되는 패턴을 찾는 것이 단순한 중복 검출 이상의 의미가 있음을 느꼈다.

추가로 생각해본 점

• 이 문제에서 KMP 알고리즘을 사용하지 않고도 풀 수 있는 방법이 있을지 고민해봤다. 단순히 브루트 포스(Brute Force)로 문자열을 비교하면 시간 복잡도가 O(n^2)로 증가하므로 비효율적일 것이다. 따라서 KMP 알고리즘이 이 문제에 적합한 선택이라는 점을 다시 한 번 느낄 수 있었다.
  또한, 패턴 매칭 알고리즘은 단순히 문자열 문제뿐만 아니라 검색 엔진이나 데이터 압축 등 다양한 곳에서 활용될 수 있다는 점!

So...

• KMP 알고리즘의 LPS 테이블: 접두사와 접미사가 일치하는 최대 길이를 기록하여 문자열 탐색의 효율성을 높인다.

• 중복되는 패턴을 제거한 최소 광고 길이: 광고 문자열에서 반복되는 부분을 제외하여 실제로 필요한 최소한의 광고 길이를 찾는다.