5. Sparse Table 예제 (18783번: Swapity Swapity Swap)

 

백준 18783번: Swapity Swapity Swap

18783번: Swapity Swapity Swap

LCA 문제를 풀어볼까 했는데, 그보다 풀어보신분들은 아시겠지만, Sparse Table의 개념과 적용에 대한 것이 상당히 중요합니다.

또한 더 쉬운 풀이가 존재하지만 쉬운 문제에서 익숙치 않은 개념을 적용해 풀어보는 것이 연습하기 좋다 생각하기 때문에 해당 문제를 가져왔습니다.

 

 

 

영어 문제라 상당히 보기 불편하네요. ^^

간단히 말씀드리면 배열의 각 데이터를 swapping 하는 것입니다. 예제를 통해서 설명을 드리겠습니다.

기호
N M K
L1 R1
L2 R2

입력 예제
7 2 2
2 5
3 7

이와 같은 데이터가 입력 됩니다.

 

N은 우리가 처리해야 할 배열의 크기입니다.

N이 5로 주어진다면

배열에 이미 {1, 2, 3, 4, 5}의 값이 순서대로 저장되어있다고 가정합니다.

 

M은 우리가 swap할 값의 범위가 주어지는 갯수입니다.

즉, 위에서 M은 2라고 주어졌으니, (2, 5), (3, 7) 두 개의 정보가 입력되었습니다.

 

K는 swap 횟수를 의미합니다.

(2, 5), (3, 7)을 순서대로 2번씩 '(2, 5), (3, 7), (2, 5), (3, 7) 이렇게 진행한 결과를 출력'해라 라는 뜻입니다.

 

이 결과는 아래와 같습니다.

1
2
4
3
5
7
6

 

우선 좀 더 이해하기 쉽게 해당 메커니즘을 그림으로 표현해보겠습니다. (N = 7)

초기 상태

그림 1. 초기 상태

(2, 5) 1회 진행

그림 2. (2, 5) swap

(3, 7) 1회 진행

그림 3. (3, 7) swap

(2, 5) 2회 진행

그림 4. (2, 5) swap

(3, 7) 2회 진행

그림 5. (3, 7) swap

 

 

이렇게 2cycle을 진행하니 같은 결과를 출력하게 됩니다.

이제 어떤 문젠지 완벽히 이해가 되셨을거라 생각합니다.

 

예제는 2번 반복이나, 최대 10억번까지 값이 들어옵니다. 또한 swapping 쿼리도 최대 100개까지 들어옵니다.

따라서 이걸 하나하나 처리한다면, 최악의 경우 O(N * M * K)의 복잡도를 가지게 됩니다.

10만 * 100 * 10억 = 10^16 (경) 정도.. 오늘안엔 절대 안끝나겠죠...?

 

따라서, 해당 과정을 좀더 빠르게 처리할 방법을 모색해야합니다.

M개의 쿼리를 K만큼 반복적으로 처리한다는 것이 무언가 줄일 수 있는 포인트겠네요.

또한, K라는 숫자를 상당히 단축시켜야한다는 것이 느껴집니다.

 

즉, M개의 쿼리를 1번 시행해보고, 이를 K번 누적해보면 되겠습니다.

이를 Sparse Table에 적용한다면 parent[N][0]은 M개의 쿼리를 1번 시행한 결과가 되겠죠.

이후 K라는 값을 이진수로 가정하고 해당 데이터의 값을 변경 시켜나가주면 됩니다.

 

따라서 우선 M개의 쿼리를 1회 시행한 후 각 인덱스(i)의 값에 따른 결과를 rotate 배열에 저장합니다.

private static void findOne(Range[] arr) {
    for(int i = 0; i < cows.length; i++) {
        cows[i] = i;
        rotate[i] = i;
    }

    for(Range r: arr) {
        int ran = r.to - r.from;
        int mod = ran % 2;
        int loop = ran / 2 + mod;

        int index = 0;
        for(int i = r.from; i < r.from + loop; i++) {       // 1 time rotating result
            swap(i, r.from + ran - index++);
        }
    }
}

private static void swap(int src, int snk) {
    int tmp = rotate[src];
    rotate[src] = rotate[snk];
    rotate[snk] = tmp;
}

 

rotate[i]의 값을 parent[i][0]로 이전합니다.

for(int i = 0; i < n; i++) {
    parent[i][0] = rotate[i];
}

 

이전한 값을 통해 전체 배열을 채워줍니다.

for(int p = 1; p < 31; p++) {                   // make n times rotating relations
    for (int cur = 0; cur < n; cur++) {
		parent[cur][p] = parent[parent[cur][p - 1]][p - 1];
	}
}

-> 저장된 값들은 sparse table 개념과 같습니다.

 

즉, cur 인덱스에서 3번 반복한 동작을 찾으려면, parent[cur][0]을 찾은 후 그의 2^1번째 부모의 값을 가져오면 됩니다.

parent[parent[cur][0]][1]이 되겠죠.

 

이제 2진수 단위로 점프하면서 최종 결과를 유도해 냅니다.

for(int i = 30; i >= 0; i--) {
	int jump = 1 << i;
	if(k < jump) continue;

	k -= jump;
	for(int j = 0; j < n; j++) {                    // rotating
		cows[j] = parent[cows[j]][i];
	}
}

위와 같이 jump 가능한 값을 찾고, 이에 따른 cow[j]의 i번째 부모를 가져오면 cows 배열(초기 값)의 jump를 유도할 수 있습니다.

유도한 값은 따로 cows 배열에 유지해줍니다.

이렇게 최종적으로 가져온 값(cows)을 그대로 출력해주면 답이 됩니다.

 

Boj17873.java

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

public class Main {
    private static int[][] parent;
    private static int[] cows;
    private static int[] rotate;

    private static final String NEW_LINE = "\n";

    private static class Range {
        int from;
        int to;

        public Range(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        parent = new int[N][31];
        cows = new int[N];
        rotate = new int[N];

        Range[] r = new Range[M];
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            r[i] = new Range(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
        }

        findOne(r);
        connection(N);

        System.out.println(rotating(N, K));
    }

    private static String rotating(int n, int k) {
        StringBuilder sb = new StringBuilder();

        for(int i = 30; i >= 0; i--) {
            int jump = 1 << i;
            if(k < jump) continue;

            k -= jump;
            for(int j = 0; j < n; j++) {
                cows[j] = parent[cows[j]][i];
            }
        }

        for(int c: cows) {
            sb.append(c + 1).append(NEW_LINE);
        }

        return sb.toString();
    }

    private static void findOne(Range[] arr) {
        for(int i = 0; i < cows.length; i++) {
            cows[i] = i;
            rotate[i] = i;
        }

        for(Range r: arr) {
            int ran = r.to - r.from;
            int mod = ran % 2;
            int loop = ran / 2 + mod;

            int index = 0;
            for(int i = r.from; i < r.from + loop; i++) {
                swap(i, r.from + ran - index++);
            }
        }
    }

    private static void swap(int src, int snk) {
        int tmp = rotate[src];
        rotate[src] = rotate[snk];
        rotate[snk] = tmp;
    }

    private static void connection(int n) {
        for(int i = 0; i < n; i++) {
            parent[i][0] = rotate[i];
        }

        for(int p = 1; p < 31; p++) {
            for (int cur = 0; cur < n; cur++) {
                parent[cur][p] = parent[parent[cur][p - 1]][p - 1];
            }
        }
    }
}

 

시간복잡도는 메소드 findOne + rotating 정도로 정의될 수 있겠습니다.

O(M * N + N * log(K)) = 100 * 10만 + 10만 * 31 = 약 1020만

그림 6. 채점 결과

 

사실 일반적인 재귀 DP로도 처리가 가능할 것 같습니다.

Sparse Table 자체가 DP를 기반으로한 개념이니, 두 방법 모두 적용해 풀어보시는 것을 추천드립니다.

 

 

추가로, 질문이나 틀린 부분 있으면 댓글 달아주세요!

빠르게 답변이나 보완하도록 하겠습니다. 감사합니다.