[BaekJoon] 3117 YouTube (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int BASE = 2;

    static int studentCount;
    static int videoCount;
    static int time;
    static int logTime;

    static int[] startVideoInfos;
    static int[][] topRecommendationVideo;

    static void input() {
        Reader scanner = new Reader();

        studentCount = scanner.nextInt();
        videoCount = scanner.nextInt();
        time = scanner.nextInt();
        logTime = calculateLog(time, BASE);
        startVideoInfos = new int[studentCount];
        topRecommendationVideo = new int[logTime + 1][videoCount + 1];

        for (int student = 0; student < studentCount; student++) {
            startVideoInfos[student] = scanner.nextInt();
        }

        for (int video = 1; video <= videoCount; video++) {
            topRecommendationVideo[0][video] = scanner.nextInt();
        }
    }

    static int calculateLog(int number, int base) {
        return (int) (Math.log(number) / Math.log(base));
    }

    /*
     * 희소 배열을 이용하여 해결한다
     * 처음 1분 영상을 시청한 후에 동영상 이동이 시작되기 때문에 총 이동횟수는 M - 1번이 된다
     * 희소 배열을 통해 1번 이동했을 때, 2번 이동했을 때, 4번 이동했을 때, 8번 이동했을 때...
     * 이렇게 2의 n제곱 형태로 각 동영상이 어떤 동영상으로 이동하는지를 구한다
     * M - 1번 이동해야 하니 2의 n제곱 수를 이용하여 이동한다
     * ex. 만약 M이 10이라면
     *  - M - 1 = 9 = 8 + 1
     *  - 즉, 8번 이동한 후에 각 동영상이 어느 동영상으로 이동하는지 먼저 구한 후에
     *  - 이동한 동영상부터 다시 1번 이동한 후에 어느 동영상으로 이동하는지 구한다
     *  - 이렇게 구한 동영상들이 최종 답이 된다
     */
    static void solution() {
        makeSparseTree();

        int[] answer = new int[studentCount];
        for (int student = 0; student < studentCount; student++) {
            answer[student] = findVideoAfterMTimes(startVideoInfos[student], time - 1);
        }

        StringBuilder sb = new StringBuilder();
        Arrays.stream(answer).forEach(video -> sb.append(String.format("%d ", video)));
        System.out.println(sb);
    }

    static void makeSparseTree() {
        for (int t = 1; t <= logTime; t++) {
            for (int video = 1; video <= videoCount; video++) {
                int nextVideo = topRecommendationVideo[t - 1][video];
                topRecommendationVideo[t][video] = topRecommendationVideo[t - 1][nextVideo];
            }
        }
    }

    static int findVideoAfterMTimes(int video, int time) {
        for (int bit = logTime; bit >= 0; bit--) {
            if ((time & (1 << bit)) != 0) {
                video = topRecommendationVideo[bit][video];
            }
        }

        return video;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

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

        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());
        }
    }
}