Q. 20364 자바 : 부동산 다툼

Q. 20364 자바 : 부동산 다툼

 

문제 : boj.kr/20364

실버 1 난이도의 문제이다.

 

트리의 정점의 수 n이 주어지고, 오리들의 수 q가 주어진다.

이후 오리들이 원하는 정점이 주어지는데,

만약 탐색 도중 다른 오리가 있다면 거기서 탐색을 멈추고 그 좌표를 출력하고

탐색이 완료되면 0을 출력한다.

 

문제는 아래와 같이 풀었다.

1. 오리들이 원하는 정점 / 2를 통해 1까지 올라온다.

2. 만약 도중에 다른 오리가 있는 정점을 만난다면 그 값을 저장한다.

3. 정점 1까지 오리가 도달했을 때 저장된 값이 있다면 그 값을, 아니면 0을 출력한다.

 

이 문제의 시간복잡도는 아래와 같다.

1. 트리 DFS 순회 - O(log N)

2. 오리의 수 Q - O(Q)

최악의 경우 오리가 순서대로 마지막 ~ 처음 정점에 존재한다면 시간복잡도는 O(QlogN)이다.

N의 최대값은 약 1,000,000 이고 Q의 최대값은 200,000이므로 시간초과는 걱정하지 않아도 된다.

 

풀이는 아래와 같다.

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int n, q;
    static int[] goal;
    static boolean[] visit;
    static void input() {

        n = scan.nextInt();
        q = scan.nextInt();
        visit = new boolean[n + 1];
        goal = new int[q];
        for (int i = 0; i < q; i++) {
            goal[i] = scan.nextInt();
        }
    }

    static void dfs(int cur, int lastVisit ,int goal) {

        if (cur == 1) {
            if (lastVisit == 0) {
                visit[goal] = true;
                sb.append(0).append('\n');
            }else {
                sb.append(lastVisit).append('\n');
            }
            return;
        }

        if (visit[cur]) {
            lastVisit = cur;
        }
        dfs(cur / 2, lastVisit, goal);
    }

    static void pro() {
        for (int i = 0; i < q; i++) {
            dfs(goal[i], 0, goal[i]);
        }
    }

    public static void main(String[] args) {
        input();
        pro();
        System.out.println(sb);
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}