백준 17225 세훈이의 선물가게

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

문제해결

출력값은 상민이와 지수가 포장한 선물 개수와 번호로 이 문제의 포인트는 상민잉와 지수의 선물 포장 시작 시간을 찾는 것이다.

1. 우선순위 큐를 이용하여 시작 시간 기준으로 오름차순 정렬한다. 비교 기준으로 시작 시간이 같으면 상민이 먼저 배정받고 그렇지 않은 경우 시간을 오름차순으로 정렬한다. 우선순위 큐는 힙 자료구조 기반이기 때문에 비교 기준이 필요하고 Comparable 인터페이스를 구현하면 비교기준에 따라 큐에 값이 저장된다.
2. 상민과 지수의 포장 시작 시간을 찾는다. bMax와 aMax 변수를 선언하여 각각 포장하는데 걸리는 시간만큼 더한 값을 큐에 추가한다.
3. 우선순위가 높은 데이터 먼저 큐에서 제거하여 인덱스를 배열 리스트에 추가한다.
4. 마지막으로 배열 리스트의 사이즈와 요소를 출력하여 답을 구한다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Order> pq = new PriorityQueue<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int bt = Integer.parseInt(st.nextToken()); // 상민이가 포장하는데 걸리는 시간
        int rt = Integer.parseInt(st.nextToken()); // 지수가 포장하는데 걸리는 시간
        int n = Integer.parseInt(st.nextToken()); // 어제 가게 손님 수

        int t, c, m;
        int bMax = 0; // 상민이의 포장 끝나는 시간
        int aMax = 0; // 지수의 포장 끝나는 시간
        for (int i = 0; i < n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            t = Integer.parseInt(st2.nextToken()); // 주문 시각
            c = st2.nextToken().charAt(0); // 포장지 색
            m = Integer.parseInt(st2.nextToken()); // 주문한 선물 개수

            for (int j = 0; j < m; j++) {
                if (c == 'B') {
                    if (bMax >= t) {
                        pq.add(new Order(bMax, 'b'));
                        bMax += bt;
                    } else {
                        pq.add(new Order(t, 'b'));
                        bMax = t + bt;
                    }
                } else {
                    if (aMax >= t) {
                        pq.add(new Order(aMax, 'a'));
                        aMax += rt;
                    } else {
                        pq.add(new Order(t, 'a'));
                        aMax = t + rt;
                    }
                }
            }
        }
        ArrayList<Integer> blue = new ArrayList<>();
        ArrayList<Integer> red = new ArrayList<>();
        int idx = 1;
        while (!pq.isEmpty()) {
            Order order = pq.poll();
            if (order.color == 'a') {
                red.add(idx);
            } else {
                blue.add(idx);
            }
            idx++;
        }
        System.out.println(blue.size());
        for (int k : blue)
            System.out.print(k + " ");
        System.out.println();
        System.out.println(red.size());
        for (int k : red)
            System.out.print(k + " ");
        System.out.println();
    }
}

class Order implements Comparable<Order> {
    int startTime; // 시작 시간
    char color; // 포장지 색

    public Order(int startTime, char color) {
        this.startTime = startTime;
        this.color = color;
    }

    @Override
    public int compareTo(Order o) {
        // 시작 시간이 같으면 상민이 먼저
        if (this.startTime == o.startTime) {
            return o.color - this.color; // R(들어온값) - B(기존값) = 양수 => 오름차순
        }
        return this.startTime - o.startTime; // 시작 시간 오름차순 정렬
    }
}

예제 입력 2에 대하여 해당 소스코드로 실행한 결과 배열리스트에 상민 - [1,2,4,5,7], 지수 - [3,6,8] 이 저장된다.

힌트에 우선순위 큐라고 나와있었지만 어떻게 풀어야하는지 감도 못잡아서 다른 사람 풀이를 여러 번 보고 그리면서 이해한 문제였다.

Reference

• https://moons-memo.tistory.com/112