Algorithm - INSERTION

문제

유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다.
예를 들어 {5, 1, 4, 3, 2}의 삽입 정렬은 다음과 같이 이루어집니다.

배열	비고
5 1 4 3 2	초기상태
1 5 4 3 2	1을 왼쪽으로 1칸 옮김
1 4 5 3 2	4을 왼쪽으로 1칸 옮김
1 3 4 5 2	3을 왼쪽으로 2칸 옮김
1 2 3 4 5	2을 왼쪽으로 3칸 옮김

1부터 N까지의 자연수가 한번씩 포함된 길이 N인 수열을 삽입 정렬했습니다. 원래 수열은 알 수 없지만, 이 과정에서 각 원소가 왼쪽으로 몇 칸이나 이동했는지를 알고 있습니다. 예를 들어, 앞의 예제에서 각 위치에 있는 값들이
움직인 칸수를 표현하면 {0, 1, 1, 2, 3}이 됩니다. 이때 원래 수열을 찾아내는 프로그램을 작서앟세요.

시간 및 메모리 제한

프로그램은 2초 안에 실행되어야 하며, 64mb 이하의 메모리를 사용해야 합니다.

입력

/테스트 케이스의 수/

/원 배열의 길이/

/배열의 각 위치에 있던 값들이 움직인 칸 수/

...

출력

각 테스트 케이스마다 재구성한 A[]를 한 줄에 출력합니다.

풀이

문제 접근 방법 자체는 굉장히 단순하다. 1부터 N까지의 자연수가 정렬된 배열 B를 하나 만들고,
움직인 칸 수가 담겨있는 배열(:= shifted)을 마지막 원소부터 거꾸로 순회하며 B[n - shifted[i] - 1]를 하나씩
차례대로 빈 배열에 저장하고, 이 원소는 원래 배열 B에서 지워나가면 된다.

일반적인 방법으로는 shifted 배열을 순회하는 데 O(N)번, n - shifted - 1 번째 원소를 찾는 데 or 삭제하는 데 O(N) 번의 탐색을 해야하므로
종합적으로 O(N^2)의 시간복잡도를 가지게 될 것이다. 그런데 이 문제에서 N의 최댓값은 50000이므로, 이렇게 해서는
시간 내에 문제를 해결할 수 없다.

그래서 임의의 k에 대하여 배열 내에서 k번째 원소를 찾아내는 작업과 이 원소를 배열에서 지우는 작업을 빠른 시간 내에 수행할 수
있는 알고리즘이 필요하다. 트립(Trip)을 이용하면 이 작업을 O(lgN) 시간에 수행할 수 있다.

TripNode라는 클래스를 만들고, 이 자료구조를 이용해 할 수 있는 작업들을 TripUtil 클래스에 작성한다.

TripNode

public class TripNode {
    private int key;
    private int priority, size;
    private TripNode left, right;

    public TripNode(int key) {
        this.key = key;
        this.priority = (int)(Math.random() * 100);
        this.size = 1;
        this.left = null;
        this.right = null;
    }

    void setLeft(TripNode left) {
        this.left = left;
        calcSize();
    }

    void setRight(TripNode right) {
        this.right = right;
        calcSize();
    }

    void calcSize() {
        this.size = 1;
        if(this.left != null) this.size += left.getSize();
        if(this.right != null) this.size += right.getSize();
    }

    int getKey() {
        return this.key;
    }

    int getPriority() {
        return this.priority;
    }

    TripNode getLeft() {
        return this.left;
    }

    TripNode getRight() {
        return this.right;
    }

    int getSize() {
        return this.size;
    }
}

TripUtil

public class TripUtil {
    static Pair<TripNode, TripNode> split(TripNode root, int key)

    public static TripNode insert(TripNode root, TripNode node);

    static TripNode merge(TripNode a, TripNode b);

    public static TripNode erase(TripNode root, int key);

    public static TripNode kth(TripNode root, int k);
}

(자세한 코드는 INSERTION/TripUtil.class 참고)

이렇게 적절한 자료구조와 이를 이용한 빠른 알고리즘을 구성해놓고 나면, 실제 문제를 해결하는 함수는 굉장히 간단하게 작성할 수 있다.

    static void solve() {
        TripNode candidates = null;
        for(int i = 0 ; i < n ; i++) {
            candidates = TripUtil.insert(candidates, new TripNode(i+1));
        }

        for(int i = n-1 ; i >= 0 ; i--) {
            int larger = shifted[i];
            TripNode k = TripUtil.kth(candidates, i + 1 - larger);
            arr[i] = k.getKey();
            candidates = TripUtil.erase(candidates, k.getKey());
        }
    }