백준 12842 튀김 소보루 자바(java)

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

12842번: 튀김 소보루

 

풀이 방법

우선순위 큐를 사용하여 풀었다.

빵은 먼저 다 먹은 순서대로 빵을 다시 집어서 먹을 수 있으며, 만약 동시에 먹게 된다면 작은 번호인 사람이 우선으로 집게 된다. 따라서, 빨리 먹은 순, 작은 번호 순을 우선순위 기준으로 하는 우선순위 큐를 생성하여 s개의 빵이 남을 때까지 차례대로 꺼내주는 방식으로 구현하였다.

이때, Person 이라는 클래스를 만들어 사람 번호와 빵을 다 먹는 시간을 저장할 수 있도록 하였으며, 우선선위 큐의 우선순위 지정을 위해 Comparable Interface를 상속 받아 compareTo 메서드를 오버라이드해주었다.

자세한 풀이 흐름은 아래와 같다.

1. 현재 남아 있는 빵의 개수를 카운트할 cnt 변수를 n으로 초기화하여 선언한다.
2. 우선순위 큐에 작은 번호 순대로 빵을 집는 사람을 집어 넣는다.
   1. 빵을 하나씩 집으면서 cnt 를 감소시킨다. <- 주의 !
   2. cnt가 s가 되면 더 이상 빵을 집지 않고 정답을 출력하고 종료한다.
3. 그 다음 큐에서 가장 먼저 빵을 다 먹게 되는 사람을 꺼내고 cnt를 감소시킨다.
4. 지금 꺼낸 사람과 동시에 빵을 다 먹게 되는 사람들을 모두 꺼내고 cnt를 감소시킨다.
5. 꺼낸 사람들마다 현재 다 먹은 시간 + 소보루를 먹는 데 걸리는 시간 으로 다시 큐에 집어 넣는다.
6. 남은 빵 개수가 s가 될 때까지 3~5번을 반복한다.

 

주의할 점!!!

처음엔 빵을 먹는 데 걸리는 시간이 t이면 t초 동안 다 먹고 그 다음 t+1에 다시 빵을 집게 되는 줄 알았지만 현재 문제에선 빵을 다 먹자 마자 바로 빵을 다시 집는 것으로 접근해야 한다. 따라서 다음 빵을 집게 되는 시간을 t초 후로 해야 한다.

t+1로 설정하면 1번 사람이 0초, 2초, 4초에 빵을 집고 2번 사람은 0초, 4초에 빵을 집는 데, 이럴 경우 1번 사람이 3개째 빵을 집을 때 2번 사람이 동시에 빵을 집게 되어 문제에 주어진 예시와 틀리게 된다!!

 

 

코드

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

public class Main {

    static class Person implements Comparable<Person>{
        int num;
        int time;

        public Person(int person, int time) {
            this.num = person;
            this.time = time;
        }

        @Override
        public int compareTo(Person o) {
            if(this.time == o.time){ // 동시에 다 먹으면
                return this.num - o.num; // 작은 번호 순
            }
            return this.time - o.time; // 빨리 먹는 시간 순
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int s = Integer.parseInt(line[1]);
        int m = Integer.parseInt(br.readLine());
        int[] people = new int[m+1];
        int answer = -1;

        for(int i=1; i<=m; i++) {
            people[i] = Integer.parseInt(br.readLine());
        }

        PriorityQueue<Person> pq = new PriorityQueue<>();

        int cnt = n; // 처음 소보루의 개수
        for(int i=1; i<=m; i++) {
            pq.add(new Person(i, people[i]));
            cnt--;
            if(cnt == s) {
                answer = i;
                break;
            }
        }

        if(answer == -1) {
            int num = -1;
            while(cnt > s) {
                Person cur = pq.poll();
                num = cur.num;
                int finishedTime = cur.time;
                pq.add(new Person(num, finishedTime + people[num]));
                cnt--;
                // 동시에 빵을 다 먹은 사람들을 작은 번호 순대로 빵 집기
                while(cnt > s && finishedTime == pq.peek().time) {
                    cur = pq.poll();
                    num = cur.num;
                    pq.add(new Person(num, finishedTime + people[num]));
                    cnt--;
                }
            }
            answer = num;
        }
        System.out.println(answer);
    }
}