20364번: 부동산 다툼

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

문제

이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다.

1. 루트 땅의 번호는 1이다.
2. 어떤 땅의 번호가 *K*라면, 왼쪽 자식 땅의 번호는 2 × *K*, 오른쪽 자식 땅의 번호는 2 × *K* + 1이다.

어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다.

1. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다.
2. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다.

만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을

지나가지 못해 그 오리는 땅을 가지지 못한다. 오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다.

경완이의 해결책대로 땅 분배를 했을 때 각 오리별로 원하는 땅을 가질 수 있는지,

가질 수 없다면 처음 마주치는 점유된 땅의 번호를 구해보자.

입력

첫 번째 줄에 땅 개수 *N*과 꽉꽉나라에 사는 오리 수 *Q*가 공백으로 구분되어 주어진다. (2 ≤ N < 220, 1 ≤ Q ≤ 200,000)

두 번째 줄부터 차례로 *Q*개의 줄에 걸쳐 i+1번째 줄에는 `i번째 오리가 원하는 땅 번호 xi`가 주어진다. (2 ≤ xi ≤ N)

출력

`Q개의 줄에 원하는 땅에 갈 수 있다면 0을, 갈 수 없다면 처음 마주치는 점유된 땅의 번호`를 출력한다.

예제 입력 1

6 4
3
5
6
2

예제 출력 1

0
0
3
0

+) 예제 입력 2

11 5
4
2
2
8
11

+) 예제 출력 2

0
0
2
2
2

풀이

• 코드가 길어지거나 지저분해지면 처음부터 다시 풀기
  • 에러 잡기도 힘들고 그렇게 오래 풀어서 맞아도 의미가 없음… 고집 ㄴㄴ
• 부모 노드를 기록할 필요도 없었던 문제
  • 부모 노드 → 현재 노드 / 2

package tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_20364 {

    private static int numberOfLand;
    private static int numberOfDuck;
    private static int[] wantLand;
    private static int[] parent;
    private static boolean[] owned;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

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

        st = new StringTokenizer(br.readLine());

        numberOfLand = Integer.parseInt(st.nextToken());
        numberOfDuck = Integer.parseInt(st.nextToken());

        owned = new boolean[numberOfLand + 1];
        wantLand = new int[numberOfDuck];

        for (int i = 0; i < numberOfDuck; i++) {
            wantLand[i] = Integer.parseInt(br.readLine());
        }
    }

    private static void process() {
        for (int i = 0; i < numberOfDuck; i++) {
            int land = wantLand[i];
            int findParent = land;
            int result = 0;

            while (findParent != 0) {
                if (owned[findParent]) {
                    result = findParent;
                }

                findParent /= 2;
            }

            if (result == 0) {
                owned[land] = true;
            }

            sb.append(result).append('\n');
        }
    }

    private static void output() {
        System.out.println(sb);
    }

}