코드트리 <번호표를 든 N명의 사람>

번호표를 든 N명의 사람

---

문제 해결

무대에 올리는 수 K를 이진탐색으로 찾아 Tmax를 넘지 않는 K의 최솟값을 찾았다.

 

maxTime 함수를 통해 K가 N일 때 걸리는 시간을 구한다. K가 N일 때는 모든 사람이 무대에 같이 올라가기 때문에 무대에 머무르는 시간이 가장 큰 사람의 시간이 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)이 된다.

 

onStage 함수는 파라미터로 주어진 k를 무대에 올릴 수 있는 최대 수라고 가정하고 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)을 구한다.

total을 구하는 것은 우선순위 큐에 무대에서 내려가야 하는 시간을 넣으면서 마지막 사람이 내려오는 시간을 구하면 된다.

1. 처음에 순서대로 k명이 무대에 머무르는 시간을 우선순위 큐에 넣는다. (처음에 올라갈 때는 현재 시간이 0이기 때문에 그냥 머무르는 시간을 넣어도 된다.)
2. 그 다음부터는 우선순위 큐에서 값을 하나 꺼내고 그 값을 현재 시간이라고 설정하고, 그 다음 순서의 사람을 무대에 올린다. 이때 해당 사람이 무대에서 내려오는 시간은 현재 시간 + 해당 사람이 무대에 머무르는 시간이 된다.
3. 당연하게도 무대에 올라갈 사람이 남아있을 때만 우선순위 큐에 넣어야 한다.

 

binarySearch 함수를 통해 무대에 올리는 수 K의 후보(mid)를 탐색한다.

1. 만약 mid를 K라고 했을 때,
2. 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)이 Tmax보다 작거나 같으면
   1. mid보다 더 적은 애들을 올려본다.
      ( 모두 무대에 올라갔다 내려오는데 걸리는 시간이 작다는 것은 무대에 올라가는 수가 많다는 뜻이기 때문에 더 적은 수를 올려보는 것이다.)
   2. Tmax보다 작기 때문에 정답 후보가 될 수 있어 Answer의 값을 더 작은 값으로 갱신한다.
3. 모두 무대에 올라갔다 내려오는데 걸리는 시간(total)이 Tmax보다 크면 mid보다 더 많은 애들을 올려본다.
   ( 모두 무대에 올라갔다 내려오는데 걸리는 시간이 크다는 것은 무대에 올라가는 수가 적다는 뜻이기 때문에 더 많은 수를 올려보는 것이다.)

---

코드

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

public class Main {
    static int N, T, Answer;
    static int[] time;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        T = Integer.parseInt(inArr[1]);
        time = new int[N];
        for (int i = 0; i < N; i++) {
            time[i] = Integer.parseInt(br.readLine());
        }
        // end input
        Answer = Integer.MAX_VALUE;
        binarySearch();
        System.out.println(Answer != Integer.MAX_VALUE ? Answer : 0);
    }

    static void binarySearch() {
        int start = 1;
        int end = N;
        while (start <= end) {
            int mid = (start + end) / 2;
            int total = mid >= N ? maxTime() : onStage(mid);
            
            if (total <= T) {   // 무대에 더 적은 애들을 올려보자
                Answer = Math.min(Answer, mid);
                end = mid - 1;
            } else {    // total > T -> 무대에 더 많은 애들을 올려야 함
                start = mid + 1;
            }
        }
    }
    static int maxTime() {
        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, time[i]);
        }
        return max;
    }

    static int onStage(int K) {
        int t = 0;
        PriorityQueue<Integer> stage = new PriorityQueue<>();   // 무대에 올라가 있는 사람들이 내려와야 하는 시간
        int idx = 0;
        for (idx = 0; idx < K; idx++) {
            stage.add(time[idx]);
        }
        while (!stage.isEmpty()) {
            t = stage.poll();
            if (idx < N) {
                stage.add(t + time[idx++]);
            }
        }
        return t;
    }
}

---

 

출처

https://www.codetree.ai/missions/8/problems/n-people-with-numbers?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석