[자바] 백준 25200 - 곰곰이와 자판기 (boj java)

문제 : boj25200

 

  에디토리얼과도 아예 다른 풀이이고, 난이도 기여의 다른 사람들 의견과도 다른 방식인걸로 보아 상당히 독특하게 푼 것 같다.

 

  당연히 N개의 음료수에 대해 M번의 차원 이동을 실제로 해보려면 현재 이동할 차원 U, V(<=N) 에 포함된 차원들을 모두 데리고 이동해야 한다. 예를들어 1->3, 3->2 라면 1->3으로 차원3에는 1과 3의 두개가 있을 것이다. 따라서 3->2는 3만 이동하면 안되고 1과 3을 둘 다 이동해야 한다. 그러므로 O(NM)의 시간복잡도가 필요하므로 통과할 수 없다.

 

  그렇다면, 첫 시작을 N개의 LinkedList로 해보면 어떨까? LinkedList[N+1] 짜리에 각각 LinkedList[1]엔 1만 있고, [2]엔 2만 있고, ... [N]엔 N만 두고 시작해보자. 그럼 M개의 쿼리에 대해 U->V로 빠르게 LinkedList를 합칠 수 있다면 적절한 시간내에 풀 수 있을 것이다. 하지만 자바에서 두 LinkedList를 합치는 addAll 함수는 아래와같이 매번 O(N)의 시간복잡도를 필요로 한다.

 

  하지만 LinkedList를 직접 구현해본 사람이라면 두 LinkedList를 O(1)에 합칠 수 있다는걸 알고 있을것이다. 각 LinkedList에 처음과 끝을 뜻하는 start, end가 있다고 생각해보자. 이 때 M개의 쿼리에서 입력받은 v와 u를 기준으로 LinkedList[v]의 end에 LinkedList[u]의 start를 붙여주고, LinkedList[v]의 end가 LinkedList[u]의 end로 바꾸는 식으로 하면 O(1)에 두 차원을 합칠 수 있다. 그럼 O(N+M)이 되므로 통과할 수 있다. 자바의 addAll로는 안되니 직접 구현해서 풀면 된다.

 

 

 

코드 : github

...
class Node {
    int num;
    Node next;
    public Node(int num) {
        this.num = num;
        this.next = null;
    }
}
class LList {
    Node st, ed;
    public LList() {
        st = ed = null;
    }
    public boolean isEmpty() {return st==null;}
    public void add(int num) {
        Node tmp = new Node(num);
        if (isEmpty()) {
            st = ed = tmp;
        } else {
            ed.next = tmp;
            ed = tmp;
        }
    }
    public void concat(LList another) {
        if (another.isEmpty()) return;
        if (isEmpty()) {
            this.st = another.st;
            this.ed = another.ed;
        } else {
            this.ed.next = another.st;
            this.ed = another.ed;
        }
        another.st = another.ed = null;
    }
}

...


private void solution() throws Exception {
    int n = nextInt();
    int m = nextInt();
    LList[] list = new LList[n+1];
    for (int i = 1; i <= n; i++) {
        list[i] = new LList();
        list[i].add(i);
    }
    while (m-->0) {
        int u = nextInt();
        int v = nextInt();
        list[v].concat(list[u]);
    }
    int[] answer = new int[n+1];
    for (int i = 1; i <= n; i++) {
        LList tmp = list[i];
        if (tmp.isEmpty()) continue;
        Node it = tmp.st;
        while (it != null) {
            answer[it.num] = i;
            it = it.next;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        sb.append(answer[i]).append(' ');
    }
    System.out.println(sb);
}