https://www.acmicpc.net/problem/17225
출력값은 상민이와 지수가 포장한 선물 개수와 번호로 이 문제의 포인트는 상민잉와 지수의 선물 포장 시작 시간을 찾는 것이다.
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] 이 저장된다.
힌트에 우선순위 큐라고 나와있었지만 어떻게 풀어야하는지 감도 못잡아서 다른 사람 풀이를 여러 번 보고 그리면서 이해한 문제였다.