[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기(Java, 간단한 코드, Union-Find)

programmers.co.kr/learn/courses/30/lessons/64062#

코딩테스트 연습 - 징검다리 건너기

 

## 접근

---

• 시뮬레이션 형태로 접근하면 절대 안된다. 시간복잡도가 대략적으로 계산해봐도 너무 크다. 따라서, 삭제해야할 돌을 우선순위큐에 넣어놓고, 순차적으로 접근한다.
  
  
  
  
• 돌이 가지고 있는 값이 지나갈 수 있는 사람의 수라고 볼 수 있다. 값이 3인 돌을 지우다가, 간격이 k보다 같거나 크면 문제가 발생하고 종료해야 한다.
  
  
  
  
• 순차적으로 돌들을 지우면서, 간격을 확인하는 방법을 생각해봐야 한다. 특정한 돌을 지울 때, 앞 뒤로 비어있는 돌들을 확인해서 값을 확인하면 된다. 앞 뒤로 비어있는 돌을 순차적으로 접근하면 시간복잡도가 초과한다.
  
  
  
  
• 결론적으로, 원하는 것은 어떤 돌이 있을 때, 앞 뒤로 비어있는 돌의 개수를 바로 파악할 수 있어야 한다. 이러한 것을 쉽게 가능하게 해주는 알고리즘이 Union-Find이다.
  
  
  
  
• 그렇다면, 왜 Union-Find인가? Union을 통해서, 값이 0이 된 돌이 다음 돌을 가르킬 수 있도록 만들어준다. Find를 통해서, 앞뒤로 순차적으로 접근하는 것이 아니라 바로 접근할 수 있도록 해준다.
  
  
  
  
• 일반적으로는 Find와 Union을 하나의 root 배열에 쓴다. 하지만, 카카오에서는 그런 일반적인 문제를 싫어하기 때문에, root 배열을 2개 선언해야 문제를 풀 수 있도록 했다. 위에서 말했듯이, 뒤나 앞만 확인하는 것이 아니라, 앞 뒤로 순차적으로 접근해야 되기 때문이다.

 

## 해설코드

---

import java.lang.*;
import java.io.*;
import java.util.*;
 
class Solution {
    int[] root;
    int[] root2;
    
    class Item{
        int idx, val;
        Item(int i, int v){
            this.idx = i;
            this.val = v;
        }
    }
    
    int find(int x){
        if(x == root[x])
            return x;
        else
            return root[x] = find(root[x]);
    }
    
    int find2(int x){
        if(x == root2[x])
            return x;
        else
            return root2[x] = find2(root2[x]);
    }
    
    void union(int x, int y){
        root[find(x)] = find(y);
    }
 
    void union2(int x, int y){
        root2[find2(x)] = find2(y);
    }
 
    public int solution(int[] stones, int k) {
        int answer = 0;
        root = new int[stones.length + 2];
        root2 = new int[stones.length + 2];
        
        for(int i = 0; i < root.length; i++) {
            root[i] = i;
            root2[i] = i;
        }
 
        PriorityQueue<Item> queue = new PriorityQueue<>(new Comparator<Item>(){
            public int compare(Item i1, Item i2){
                if(i1.val == i2.val){
                    return Integer.compare(i1.idx, i2.idx);
                }else
                    return Integer.compare(i1.val, i2.val);
            }
        });
        
        for(int i = 0; i < stones.length; i++ ){
            queue.add(new Item(i + 1, stones[i]));
        }
        
        while(queue.size() != 0){
            Item item = queue.poll();
            boolean flag = false;
            
            while(queue.size() != 0){
                union(item.idx, item.idx + 1);
                union2(item.idx, item.idx - 1);
                
                int val = Math.abs(find(item.idx) - item.idx) + Math.abs(find2(item.idx) - item.idx) - 1;
                if(val >= k){
                    flag = true;
                    break;
                }
                
                if(queue.peek().val != item.val)
                    break;
                
                item = queue.poll();
            }
            
            if(flag){
                answer = item.val;
                break;
            }
            
            answer = item.val;
        }
        
        return answer;
    }
}