[백준 / BOJ] 1097 마법의 단어

문제

출처 : https://www.acmicpc.net/problem/1097

1097번: 마법의 단어

N개의 단어가 있다.

N개의 단어를 적절히 조합하여 (이때, N개의 단어를 전부 사용해 조합해야한다) 문자열 T를 만든다.

문자열 T의 시작지점을 i만큼 오른쪽으로 이동시켰을때 문자열을 T(i)라 한다. 

(문자열 ABCD를 오른쪽으로 2만큼 움직인후 문자열은 CDAB가 된다.)

이때, 문자열 T와 바뀐문자열 T(i)가 정확히 일치하게되는 i가 k개 있으면, 이 문자열을 "마법의 단어"라고 한다.

 

"마법의 단어"를 만드는 단어 조합을 찾는 문제다.

---

풀이

해석이 어렵다.

KMP를 이용해 푼 문제였다.

 

문제를 풀때는 직관으로 KMP같은데? 라고 생각하고 몇가지 테스트케이스를 만들어가며 풀었다.

- 문자열 T를 i칸 이동시켰을때 문자열T(i)가 문자열 T와 같은지 확인해야한다. 

- 문자열의 접두사와 접미사가 연속적으로 일치하면 이 문자열은 T = T(i)이다.

몇가지 예시를 보자.

 

1.

ABCDABCD

희소 배열은 00001234 이며, 

i = 4일때, T = T(i)이다.

 

2.

ABCABCABC

희소배열은 000123456 이며,

i = 3, 6 일때, T = T(i)이다.

 

뭔가 느낌이 온다.

 

문자열 ABCABCABC를 기준으로 생각해보자.

희소배열에 따르면, 이 문자열은 ABC = ABC, ABCABC = ABCABC와 같이 겹치는것을 알수있다.

ABCABC = ABCABC와 같은형태로 겹친다는것은, (KMP를 통해 겹치는 부분을 구해줬기때문에,) ABCABCABC = ABCABCABC와 같은형태로 겹친다는것과 똑같은 의미다.

 

이를 통해 공식을 만들수있다.

(i = 0인 경우를 제외하기위해서, K-1을 해준다.)

K-1 == pi[word.length()-1] / (word.length()-pi[word.length()-1]) ? 1 : 0;

이때, word는 T와 같은 의미이며, pi는 희소배열이다.

위 조건을 만족하면, T(i) = T를 만족하는 i가 k개 존재하는것이므로 1을 반환한다.

 

kmp소스코드

    private int kmp(String word){
        int[] pi = new int[word.length()+5];
        int pIdx = 0;
        for(int idx = 1; idx < word.length(); idx++){
            while(word.charAt(idx) != word.charAt(pIdx) && pIdx > 0) pIdx = pi[pIdx-1];
            if(word.charAt(idx) == word.charAt(pIdx)) pi[idx] = ++pIdx;
        }
        if(pi[word.length()-1] % (word.length()-pi[word.length()-1]) != 0){
            if(K == 1) return 1;
            else return 0;
        }
        return K-1 == pi[word.length()-1] / (word.length()-pi[word.length()-1]) ? 1 : 0; 
    }

예외처리하는 if구문을 유심히 보도록 하자.

 

찾은 반례

1

ABCDABCDABC

1

답 : 1

 

1

ABCABCABC

3

답 : 1

 

1

ABCABCABCDEF

1

답 : 1

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1097%20%EB%A7%88%EB%B2%95%EC%9D%98%20%EB%8B%A8%EC%96%B4/Main.java

devxb/JJUNalgo