[BOJ 20364] 부동산 다툼 (Java, Tree)

 

---

문제 링크

https://www.acmicpc.net/problem/20364

20364번: 부동산 다툼

---

문제 풀이

- 노드가 최대 2^20 개이고, 부모 노드로 올라갈 시 log만큼 줄어듦, 그리고 Q 가 최대 20만

- 시간 복잡도 O(20만 * log2^20) = 400만

- 주어진 Q에 대해 거꾸로 부모 노드를 올라가면서 점유지가 없을 경우 0을 출력하고, 있을 경우 가장 마지막에 찾은 점유지(=가장 처음 부딪히게 될 점유지)를 출력하여 됨 

 

6번의 경우 3번 점유지로 인해 통과 못함

부모 노드 = (int) 현재 노드 / 2 

 

실수*

최종적으로 Q노드 부터 Root 노트까지 올라가면서 마지막 점유지를 찾는건데, break를 잘못 걸어서 틀렸었음

예) 위에 그림에서 1번 노드도 점유 되어 있을 경우, 6번 병아리가 출발한다면 처음 부딪히게 되는 점유지는 1이 되야함

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {

    static StringBuilder sb = new StringBuilder();

    static int N, Q;

    static boolean[] REAL_ESTATE;

    static List<Integer> query = new ArrayList<>();

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        REAL_ESTATE = new boolean[N + 1];

        for(int i = 1; i <= Q; i++) {
            st = new StringTokenizer(br.readLine());
            query.add(Integer.parseInt(st.nextToken()));
        }

        br.close();
    }

    static void execute(int target) {
        int result = 0;
        int idx = target;

        while(idx != 0) {
            if(REAL_ESTATE[idx]) { // break 잘못 걸어서 틀림
                result = idx;
            }

            idx /= 2;
        }

        if(result == 0) REAL_ESTATE[target] = true;
        
        sb.append(result).append("\n");
    }
    
    static void pro() {
        for(int q : query) execute(q);
 
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}