삽입 정렬 뒤집기 풀이

• 문제(알고스팟): https://algospot.com/judge/problem/read/INSERTION
• 제한시간: 2초

문제에서 주의할 점

• 배열 N (1 <= N <= 50000)
• 테스트 케이스 수 C(1 <= C <= 50)

문제에서 주어진 힌트

• 결국 정렬이 이루어지면 1 ~ N 형태의 모양을 가지게 된다.
• 입력값이 어떤 숫자가 초기상태에서 이동한 (옮긴) 횟수가 된다.
• 따라서 입력값 배열의 맨 마지막 수 (입력값이 0 1 1 2 3 이면 3부터) 부터 하나씩 초기상태의 값을 유추 할 수 있다.
• 구하려는 답인 초기상태는, 최종적으로 정렬이 되어져 있다고 했을때, (현재 정렬 되어있다는 배열의 전체 수 - 입력값)을 index로 가지는 수가 된다.
  • 아래 예를 들어본다.
    • 루틴1
      • 0 1 1 2 3 이 입력값
      • 1 2 3 4 5 가 결국 최종적으로 정렬되서 나타나는 모양
      • 입력값중 맨 뒤쪽값 3
      • 현재 정렬되서 있는 모양의 Size(5) - 3 = 2 (2번째 index 값) 2를 찾게 됨
      • 현재 답 >> ? ? ? ? 2
    • 루틴2 - 맨뒤 2는 찾았을때
      • 0 1 1 2 이 남은 입력값
      • 1 3 4 5 가 남은 정렬된 형태의 수
      • 입력값중 맨 뒤쪽값 2
      • 현재 정렬되서 있는 모양의 Size(4) - 2 = 2 (2번째 index 값) 3을 찾게 됨
      • 현재 답 >> ? ? ? 3 2
  • 위 루틴을 반복하면 5 1 4 3 2 라는 답을 구할 수 있다.

Java에서 일반 배열이나 LinkedList을 사용하는 경우, n 번째 index 값을 가져오는 부분과, 기존 배열에서 특정 item 을 하나 지우는 동작의 경우 list가 크면 클 수록 느리다. 따라서 트립(Treap)형태로 이진 트리를 직접 구성하고, 이미 정렬된 형태의 수를 구성한 이후 주어지는 입력값 (== n번째 값)을 구하고, 트리를 갱신 (남은 정렬된 형태의 수로 만듬)을 하는 형태를 취해야 한다.

풀이코드

Java로 풀이함

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {
    static class TreapNode {
        public static final Random r = new Random();
        public int value;
        public int priority;
        public int size;
        public TreapNode left;
        public TreapNode right;

        public TreapNode(int value, TreapNode left, TreapNode right) {
            super();
            this.value = value;
            this.priority = r.nextInt();
            this.left = left;
            this.right = right;
            this.size = 1;
        }

        public void resetSize() {
            this.size = 1;

            if (this.left != null) {
                size += this.left.size;
            }

            if (this.right != null) {
                size += this.right.size;
            }
        }
    }

    static class NodePair {
        TreapNode low, high;

        public NodePair(TreapNode low, TreapNode high) {
            super();
            this.low = low;
            this.high = high;
        }
    }

    // [0] 은 기준값보다 작은거, [1]은 기준값보다 큰거
    // key는 기준값
    public static NodePair split(int value, TreapNode node) {
        if (node == null) {
            return new NodePair(null, null);
        }

        if (node.value < value) {
            NodePair pair = split(value, node.right);
            node.right = pair.low;
            node.resetSize();
            return new NodePair(node, pair.high);
        }

        NodePair pair = split(value, node.left);
        node.left = pair.high;
        node.resetSize();
        return new NodePair(pair.low, node);
    }

    public static TreapNode insert(TreapNode newNode, TreapNode rootNode) {
        if (rootNode == null) {
            return newNode;
        }

        if (rootNode.priority < newNode.priority) {
            NodePair pair = split(newNode.value, rootNode);
            newNode.left = pair.low;
            newNode.right = pair.high;
            newNode.resetSize();
            return newNode;
        }

        // newNode priority가 작고 (자식이 되고), value가 작으면 왼쪽
        if (newNode.value < rootNode.value) {
            rootNode.left = insert(newNode, rootNode.left);
        } else {
            rootNode.right = insert(newNode, rootNode.right);
        }
        rootNode.resetSize();
        return rootNode;
    }

    public static TreapNode getNIndexNode(int index, TreapNode node) {
        int LSize = node.left != null ? node.left.size : 0;

        if (index == LSize + 1) {
            return node;
        } else if (index <= LSize) {
            return getNIndexNode(index, node.left);
        }

        // else if (index > LSize) {
        return getNIndexNode(index - LSize - 1, node.right);
    }

    public static TreapNode merge(TreapNode lower, TreapNode higher) {
        if (lower == null) {
            return higher;
        }
        if (higher == null) {
            return lower;
        }

        if (lower.priority < higher.priority) {
            higher.left = merge(lower, higher.left);
            higher.resetSize();
            return higher;
        }

        lower.right = merge(lower.right, higher);
        lower.resetSize();
        return lower;
    }

    public static TreapNode delete(TreapNode delNode, TreapNode rootNode) {
        if (rootNode == null) {
            return rootNode;
        }

        if (delNode.value == rootNode.value) {
            rootNode = merge(rootNode.left, rootNode.right);
        } else if (delNode.value < rootNode.value) {
            rootNode.left = delete(delNode, rootNode.left);
            rootNode.resetSize();
        } else if (delNode.value > rootNode.value) {
            rootNode.right = delete(delNode, rootNode.right);
            rootNode.resetSize();
        }
        return rootNode;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int C = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < C; tc++) {
            int N = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());

            // create tree
            TreapNode root = null;
            int shift[] = new int[N];
            for (int n = 0; n < N; n++) {
                root = insert(new TreapNode(n + 1, null, null), root);
                shift[n] = Integer.parseInt(st.nextToken());
            }

            // get solution
            int[] sol = new int[N];
            for (int s = N - 1; s >= 0; s--) {
                int ATailValue = shift[s];

                TreapNode node = getNIndexNode(s + 1 - ATailValue, root);
                root = delete(node, root);
                sol[s] = node.value;
            }

            for (int p = 0; p < N; p++) {
                bw.write(String.valueOf(sol[p]));
                bw.write(" ");
            }
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();
    }
}