[Java] BOJ20364, 백준 - 부동산 다툼

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

20364번: 부동산 다툼

문제가 트리 구조이긴 하지만 트리 내부구조가 순차적으로 1씩 증가하는 것을 알 수 있기 때문에 그냥 2의 거듭제곱을 이용해주면 잘 풀 수 있다.

2 <= N < 2^20이기 때문에 트리의 최대 높이는 20, 즉 한 노드를 탐색하는데 최대 20의 시간이 걸리며 오리의 수는 최대 200,000이다.

총 탐색의 경우의 수는 20*200,000 = 4,000,000

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = parse(st.nextToken()); // 땅 개수
		int q = parse(st.nextToken()); // 꽊꽊나라 오리 수

		boolean[] visit = new boolean[n + 1];
		StringBuilder sb = new StringBuilder();
		while (q-- > 0) {
			int duck = parse(br.readLine()); // 오리가 갖고싶은 땅 번호
			int tmp = duck;

			int ground = 0;
			while (tmp > 1) {
				if (visit[tmp]) {
					ground = tmp;
				}
				tmp /= 2;
			}
			if (ground == 0) {
				visit[duck] = true;
			}
			sb.append(ground + "\n");
		}
		System.out.println(sb);
	}

	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}