15231. 바이너리 트리 JAVA

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYLnPaLqvY8DFATf 

SW Expert Academy

 

---

 

1차 시도 - 답안 아님

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

at SWEA15231.main(SWEA15231.java:24)

발생함

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

public class SWEA15231 {
	public static int N;
	public static int V;
	public static int result;
	public static boolean[][] tree_map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			N = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());
			result = 0;
			
			tree_map = new boolean[N+1][N+1];
			
			for (int i = 2; i <= N; i++) {
				int a = i / 2;
				tree_map[a][i] = true;
				tree_map[i][a] = true;
			}
			
			boolean[] visited_node = new boolean[N+1];
			visited_node[V] = true;
			
			get_distance(visited_node, V, 0);
			System.out.printf("#%d %d\n", test_case, result);
		}
	}
	
	public static void get_distance(boolean[] visited_node, int start_node, int current_distance) {
		boolean all_visited = true;
		for (boolean v_node : visited_node) {
			if (!v_node) {
				all_visited = false;
			}
		}
		
		if (all_visited) {
			if (current_distance > result) {
				result = current_distance;
			}
			return;
		}
		
		boolean isMoreGo = false;
		for(int i=1; i<=N; i++) {
			if (visited_node[i] || i == start_node) {
				continue;
			}
			
			if (tree_map[start_node][i]) {
				isMoreGo = true;
				visited_node[i] = true;
				get_distance(visited_node, i, current_distance + 1);
				visited_node[i] = false;
			}
		}
		
		if (!isMoreGo) {
			if (current_distance > result) {
				result = current_distance;
			}
			return;
		}
	}
}

 

---

 

진짜 답안

import java.util.Scanner;
import java.io.FileInputStream;
 
class Solution
{
    private static int N,V;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
         
            N = sc.nextInt();
            V = sc.nextInt();
             
            int totalH =  log2(N);
            int currentH =  log2(V);
             
            int from = (int)Math.pow(2, currentH);
            int to = (int)Math.pow(2, currentH+1);
             
            int mid = (from+to)/2;
             
            boolean left = true;
            if (V >= mid) {
                left = false;
            }
             
             
            int fromt = (int)Math.pow(2, totalH);
            int tot = (int)Math.pow(2, totalH+1);
             
             
             
            int midt = (fromt+tot)/2;
             
            int answer = currentH;
             
            if (V == 1 || (left && N >= midt) || (!left && N >= fromt)) {
                answer += totalH;
            } else {
                answer += (totalH -1);
            }
             
             
            System.out.println(String.format("#%d %d", test_case, answer));
        }
    }
     
    public static int log2(int num) {
        if (num==1)return 0;
         
        int cur = 1;
        int cnt = 0;
        while(true) {
            cnt ++;
            cur = cur*2;
            if (cur > num) break;
        }
        return cnt-1;
    }
}

 

---

 

Java  왜 이렇게 어렵냐,,,😭😭😭