백준 17225 - 세훈이의 선물가게
Updated:
Java
17225 번 - 세훈이의 선물가게
문제
세훈이는 선물가게를 운영한다. 세훈이의 선물가게는 특이하게도 손님이 어떤 선물을 구매할지 선택할 수가 없다. 대신 세훈이의 취향으로 랜덤하게 준비된 선물 중 몇 개를 구매할 것인지, 파란색과 빨간색 중 어떤 색으로 포장 받을 것인지만 결정해 주문할 수 있다.
상민이와 지수는 세훈이의 가게에서 선물 포장을 맡은 아르바이트생이다. 손님들은 파란색 포장지를 원하면 상민이에게, 빨간색 포장지를 원하면 지수에게 주문을 한다. 두 사람은 각자 주문을 받으면 그때부터 포장을 시작하는데, 현재 남아있는 선물 중 가장 앞에 있는 선물을 가져와 포장하고 주문을 받은 개수만큼 이를 반복하는 형태다. 이때 선물 하나를 포장하는 데 상민이는 A초, 지수는 B초가 걸린다. 두 사람 모두 받거나 밀린 주문이 없는데 미리 선물을 가져오거나 포장하는 일은 없으며, 두 사람이 동시에 선물을 가져올 때는 알바짬이 조금 더 있는 상민이가 먼저 가져오고, 지수가 그 뒤의 선물을 가져온다.
세훈이는 어제 구매한 선물이 망가져 있다는 항의 전화를 받았다. 자신이 준비한 선물에는 문제가 없었기에 손님에게 포장지의 색을 물었지만, 손님은 자신이 받은 선물이 무엇인지만 말하며 화를 낼 뿐이었다. 어쩔 수 없이 세훈이는 어제 가게를 방문한 손님들의 주문 내역을 보고 그 선물을 누가 포장했는지 파악하려 한다.
방문한 손님의 수와 각 손님이 주문한 시각, 선택한 포장지, 포장 받을 선물의 개수가 주어졌을 때 상민이와 지수가 각자 어떤 선물들을 포장했는지 알아내는 프로그램을 작성해보자.
접근 방법
문제에서 요구하는 것은 상민이와 지수가 포장한 선물들에 순서를 부여하는 것이다.
- 상민이와 지수가 각 선물을 포장할 때의 시작 시간을 기록한다.
- 앞서 기록한 각 선물의 포장 시간을 확인하며 순서를 부여한다.
- 상민이와 지수가 포장한 선물의 개수와 시간을 출력한다.
구현
상민(B)와 지수(R)가 각 선물을 포장하는 시작 시간을 담는 Queue를 2개 생성한다.
손님의 주문 시간에서 부터 m개 까지 포장 하는데 걸리는 시간 A, B의 간격에 따라 위 queue에 저장한다.
예를 들어, 상민이의 포장 시간이 2초이고, 1초에 3개의 선물을 주문 했으면, 상민의 Queue에 [1, 3, 5]를 저장한다.
만약 다음 손님이 또 상민이에게 6초에 2개를 주문하는 상황이 오면, 상민은 7초에 포장이 끝나므로, 7초부터 포장을 시작하여 [1, 3, 5, 7 ,9]가 된다.
위 과정을 반복하면, 다음과 같이 상민 / 지수의 queue에 선물 포장 시작 시간이 다 저장되어 있다.
상민 : [1, 3, 5, 7, 9]
지수 : [4, 7, 12]
이제 위 선물들의 순서를 부여해야 하며, 이는 while문을 통해 시간을 증가 시키며 queue에 현재 시간에 맞는 선물이 있으면, pop을 하며 순서를 부여한다.
첫 번째 예제와 같이 포장 시간이 0초인 [1, 1, 1] 상황을 방지하기 위해 peek으로 한번 더 확인한다.
코드
/*
17225번 - 세훈이의 선물가게
https://www.acmicpc.net/problem/17225
*/
import java.util.*;
import java.io.*;
public class Main {
public static void main(String []args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int bS = stoi(stk.nextToken());
int rS = stoi(stk.nextToken());
int csNum = stoi(stk.nextToken()); // customer number
int time, pNum, bTime = 0, rTime = 0; // 왼쪽부터 손님이 주문하는 시간, 물건의 개수 , 상민의 포장이 끝날때 까지 걸리는 시간, 지수의 포장이 끝날 때 까지 걸리는 시간
char color;
Queue<Integer> bp = new LinkedList<Integer>();
Queue<Integer> rp = new LinkedList<Integer>();
// 주문 및 포장
while(csNum-- != 0) {
stk = new StringTokenizer(br.readLine());
time = stoi(stk.nextToken());
color = stk.nextToken().charAt(0);
pNum = stoi(stk.nextToken());
if(color == 'B') { // 상민이의 경우
if(time < bTime) // 만약 손님을 받은 시간에 아직까지 포장을 하고 있으면 포장이 끝나는 시간으로 변경 해준다.
time = bTime;
for(int i = 0; i < pNum; i++) { // 주문한 선물의 개수만큼 반복
bp.offer(time); // 포장 시작
time += bS; // 포장 시간 간격으로 증가
bTime = time; // 마지막 포장이 끝나는 시간
}
}
else { // 지수의 경우, 상민과 동일
if(time < rTime)
time = rTime;
for(int i = 0; i < pNum; i++) {
rp.offer(time);
time += rS;
rTime = time;
}
}
}
// 포장 끝, 포장한 선물들의 번호 부여
int curT = 0, idx = 1; // curT는 시간, idx는 선물의 번호
ArrayList<Integer> ba = new ArrayList<>();
ArrayList<Integer> ra = new ArrayList<>();
while(!bp.isEmpty() || !rp.isEmpty()) {
if(!bp.isEmpty() && curT == bp.peek()) { // 현재 시간에 상민이 포장을 했으면.
ba.add(idx++);
bp.poll();
if(!bp.isEmpty() && curT == bp.peek()) // 현재 시간에 상민이 또 포장을 했으면,
continue;
}
if(!rp.isEmpty() && curT == rp.peek()) {
ra.add(idx++);
rp.poll();
if(!rp.isEmpty() && curT == rp.peek())
continue;
}
curT++; // 시간이 증가한다.
}
// 상민이가 포장한 선물의 개수, 번호 / 지수가 포장한 선물의 개수, 번호
System.out.println(ba.size());
for(int v : ba)
System.out.print(v + " ");
System.out.println();
System.out.println(ra.size());
for(int v : ra)
System.out.print(v + " ");
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
난이도
⭐⭐★★★
후기
Queue를 이용하면 쉽게 해결 할 수 있는 문제.
개선할 점
없
