20364 부동산 다툼

DONGJIN IM·2022년 3월 8일

코딩 테스트

목록 보기

62/137

문제 이해

루트 땅의 번호는 1번, K의 왼쪽 자식의 번호는 2K, 오른쪽 자식 번호는 2K+1이다.
이 때 많은 오리들이 땅을 "순서대로" 가지려고 한다.

하지만 조건이 있는데, Root ⇒ 원하는 땅으로 가는 길에 어떤 오리가 점유한 땅을 만나면 그 오리는 원하는 땅을 가지지 못한다.
(즉, 가는 길에 어떠한 땅도 점령되어 있으면 안됨)

원하는 땅을 가질 수 있으면 0, 그럴 수 없으면 원하는 땅을 가지지 못하게 하는 땅 중 "처음 만나는" 땅의 번호를 출력하는 문제이다.

문제 풀이

K의 부모 번호는 무엇일까? 바로 K/2이다. (자바의 나누기는 나머지를 버리기 때문)
따라서 visit 배열을 하나 준비한다.
이후, visit[K] ⇒ visit[K/2] ⇒ visit[K/4] ⇒ ... ⇒ visit[1]까지 검사한다.
만약 중간 visit이 모두 False라면 해당 땅을 소유할 수 있는 것이다. visit[K] = true이다.
하지만 한 개라도 True를 만나면, 그 땅은 이미 다른 오리에 의해 소유되어 있다는 의미이므로 땅을 소유할 수 없을 것이다. 따라서 visit[K] = false이다.

visit[K] = false가 되더라도 visit[1]까지 모든 visit을 검사해봐야하는데, 이유는 "처음 마주치는" 점유된 땅의 번호를 출력해야 하기 때문에, visit[T] = true인 T 중 최소값을 찾아야 하기 때문이다.

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static boolean[] visit;
	
	static Integer find_first(int start) {
        // 땅을 소유하고 있어 특정 땅을 못 얻을 경우, 
        // 처음 마주치는 점유된 땅의 번호를 구하는 방법
		int tmp = start;
		int ans = tmp; 
        // start에서 visit[start] = false여서 이 메서드가 실행된 것
		while(true) {
			if(tmp==1) break;
			
			tmp = tmp/2;
			if(!visit[tmp]) ans = tmp; 
            // ans를 계속해서 2로 나누는 값이 tmp이므로, 항상 tmp <= ans
		}
		return ans;
	}
	
	static void to_root(int start) {
		int tmp = start;
		while(true) {
			if(tmp==1) { 
            // 1번 땅은 오리들이 위치해 있는 땅으로, 누구도 소유할 수 없음 
				break;
			}
			
			if(!visit[tmp]) {
                // 누군가 땅을 소유하고 있다.
				sb.append(find_first(start)).append("\n");
				return;
			}
			
			tmp = tmp/2;
		}
		visit[start] = false; 
        // if(!visit[tmp])가 실행되지 않음. 즉, 소유할 수 있는 땅
		sb.append(0).append("\n");
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int N = sc.nextInt();
		visit = new boolean[N+1];
		
		for(int i =1;i<N+1;i++) {
			visit[i] = true;
		}
		
		int K = sc.nextInt();
		
		for(int i =0;i<K;i++) {
			int tmp = sc.nextInt();
			to_root(tmp);
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}