순한 수열

순한 수열

 

백준 12104번 문제

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

12104번: 순환 순열

 

 

 

1. 문제

 

 

2. 풀이

2.1 풀이 방법

 

문제에서 요구하는 대로, B 순열을 왼쪽으로 이동시키며 A와 같아지는 경우를 찾으면 된다.

 

예를 들어 아래와 같은 순열이 주어졌다고 하자.

 

[순열 예_그 1]

 

 

B 순열을 왼쪽으로 한 칸씩 이동시키면서 A와 같아지는지를 확인한다.

 

[순열 예_그 2]

 

 

이 예제의 경우 B 순열을 4번 이동 시키면 A와 같아지고 이 경우를 제외하고 같아지지 않는다.

 

[순열 예_그 3]

 

위 방식으로 문제를 풀 경우, (순열을 이동 시키는 경우) x (A와 B 순열이 같은지 비교하는 수)로 시간 복잡도가 O(N^2)이 된다.

 

A와 B순열이 같은지 비교할 때, equal()을 쓰면 문제가 풀리긴 하지만 시간 효율이 썩 좋진 않다.

 

[순환 방식 시간]

 

4.6초 정도로 채점하는데도 시간이 꽤 걸렸다

 

 

 

이 문제는 B순열 + B순열에서 A순열을 찾는 것으로 풀 수 도 있다(B순열 + B순열에서 마지막 문자는 제외).

 

[B순열 + B순열 예_그 1]

 

(B순열 + B순열)의 부분순열에서 B순열을 순환시킨 모든 순열을 찾을 수 있다.

따라서 (B순열 + B순열)에서 A순열이 나타나는 개수가 B순열을 순환시켰을 때, A순열과 같아지는 경우의 수가 된다.

 

 

이 예제의 경우 아래와 같이  (B순열 + B순열)에서 단 한번 A순열을 찾을 수 있다.

 

[B순열 + B순열 예_그 2]

 

문자열에서 특정 문자열을 찾는 것은 KMP 알고리즘을 사용하면 된다.

 

[kmp 방식 시간]

 

순열을 순환하는 방식과 비교하면 확실히 빠르다.

 

 

 

2.2 코드

[preprocessing]

private static int[] preprocessing(String target) {

        int[] prefixArr = new int[target.length()];
        prefixArr[0] = 0;

        int j = 0;
        for (int i = 1; i < target.length(); i++) {
            while (j > 0 && target.charAt(i) != target.charAt(i)) {
                j = prefixArr[j - 1];
            }

            if (target.charAt(i) == target.charAt(j)) {
                prefixArr[i] = j + 1;
                j++;
            } else {
                prefixArr[i] = 0;
            }
        }

        return prefixArr;
    }

 

A순열의 prefix Array를 구하는 메서드

 

 

[kmp]

private static int kmp(String text, String target) {

    int count = 0;
    int[] prefixArr = preprocessing(target);

    int j = 0;
    for (int i = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != target.charAt(j)) {
            j = prefixArr[j - 1];
        }

        if (text.charAt(i) == target.charAt(j)) {
            j++;
            if (j == target.length()) {
                count++;
                j = prefixArr[j - 1];
            }
        }
    }

    return count;
}

 

B순열 + B순열에서 A순열을 찾는 메서드

A순열을 찾을 때 마다 count에 1을 더해준다.

kmp 알고리즘을 사용하였다.

 

 

[main]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String target = new StringTokenizer(br.readLine()).nextToken();
    String text = new StringTokenizer(br.readLine()).nextToken();

    text = new StringBuffer(text)
            .append(text)
            .deleteCharAt(text.length() * 2 - 1).toString();

    int result = kmp(text, target);

    System.out.println(result);
}

 

입력을 받고 (B순열 + B순열)을 만들어서 kmp 알고리즘을 적용한다.

 

 

 

3. 전체 코드

[전체 코드]

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

public class 순환_순열_kmp_12104 {

    private static int[] preprocessing(String target) {

        int[] prefixArr = new int[target.length()];
        prefixArr[0] = 0;

        int j = 0;
        for (int i = 1; i < target.length(); i++) {
            while (j > 0 && target.charAt(i) != target.charAt(i)) {
                j = prefixArr[j - 1];
            }

            if (target.charAt(i) == target.charAt(j)) {
                prefixArr[i] = j + 1;
                j++;
            } else {
                prefixArr[i] = 0;
            }
        }

        return prefixArr;
    }

    private static int kmp(String text, String target) {

        int count = 0;
        int[] prefixArr = preprocessing(target);

        int j = 0;
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != target.charAt(j)) {
                j = prefixArr[j - 1];
            }

            if (text.charAt(i) == target.charAt(j)) {
                j++;
                if (j == target.length()) {
                    count++;
                    j = prefixArr[j - 1];
                }
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = new StringTokenizer(br.readLine()).nextToken();
        String text = new StringTokenizer(br.readLine()).nextToken();

        text = new StringBuffer(text)
                .append(text)
                .deleteCharAt(text.length() * 2 - 1).toString();

        int result = kmp(text, target);

        System.out.println(result);
    }
}