백준 20364번: 부동산 다툼

문제 설명

• 완전이진트리에서 특정 위치를 찾아가야 합니다. 이때 자신이 가는 경로에 누군가가 최종방문한 기록이 있다면 자신이 원하는 위치에 도달할 수 없습니다.

접근법

• 완전이진트리이기 때문에 자식/2 = 부모가 됩니다.
  • 그렇기 때문에 시작점(1)부터 목표지점(num)으로 가는 방법보다, 목표지점(num)에서 시작점(1)으로 가는 방법을 찾는 게 더 쉽습니다.(계속해서 2로 나누면 되기 때문에)
  • 역추적할 때 주의해야 할 점은 처음 마주하는 땅을 찾아야 한다는 점입니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		boolean[] v = new boolean[N+1];
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			int num = Integer.parseInt(br.readLine());
			sb.append(func(num,v)+"\n");
		}
		System.out.println(sb.toString());
	}
	
	public static int func(int x, boolean[] v) {
		int road = x;
		int candi = 0; // 세금을 내야 하는 땅 후보군
		while(road>1) {
			if(v[road]) {
				candi = road; // 이미 방문한 곳이 또 등장할 수 있기 때문에 return이 아니라 값을 변경합니다.
			}
			road/=2;
//			road >>= 1;
		}
        // candi의 값이 바뀌지 않았다 == 세금을 내야하는 땅이 없었다
		if(candi == 0) {
			v[x] = true;
			return 0;					
		}else {
			return candi;
		}
	}
	
}

기타

속도비교
1. BufferedReader + 비트 연산 -> 432ms
2. BufferedReader + 나눗셈 연산 -> 440ms
3. Scanner + 나눗셈 연산 -> 1128ms