[Baekjoon] 17612_쇼핑몰

Gold II

문제(출처: https://www.acmicpc.net/problem/17612)

---

< 쇼핑몰 >

 

문제 풀이 

 

우선순위 큐를 사용해서 문제를 해결했다.

 

이 문제에서 중요한 부분은 계산을 마친 고객의 시간이 동일할 때 아래와 같이 구현하는 것이다.

 

1) 계산대의 번호가 높은 고객이 먼저 나감

2) 그다음 고객은 계산대의 번호가 작은 곳으로 감

 

위와 같은 조건을 해결하기 위해 우선순위 큐를 [시간, 계산대 번호, 회원 번호]로 저장하면서 시간이 적은 순+ 계산대 번호가 큰 순으로 정렬하도록 초기화했다.

여기서 시간은 앞에 사람이 마친 시간 + 고객이 구입한 물건의 수로 선언한다. 고객의 물건의 수로만 한다면 언제 계산을 시작해서 언제 끝나는지 모르기 때문이다.

 

문제에서 출력값이 int 범위를 넘어갈 수 있음에 유의하라 했으므로 출력값을 구해줄 때는 long 타입으로 변환한 후 계산해서 더해줘야 한다.

 

 my solution (Java)

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

public class _17612_ { // 쇼핑몰

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		// 고객 수, 계산대 수
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0])
					return o2[1] - o1[1];
				return o1[0] - o2[0];
			}
		});

		int idx = 0;
		int r = 1;
		long result = 0;

		boolean arr[] = new boolean[k];
		int i = 0;
		boolean flag = false;

		while (i < n) {
			// 고객 정보
			st = new StringTokenizer(bf.readLine());
			i += 1;
			int id = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			// 아직 계산대가 비어있음
			if (queue.size() < k) {
				queue.add(new int[] { w, idx, id });
				arr[idx] = true;
				idx += 1;
			}

			// 비어있는 곳이 없음
			else {
				int temp[] = queue.poll();
				result += new Long(temp[2]) * new Long(r);
				r += 1;
				arr[temp[1]] = false;
				flag = false;
                
                // 계산을 마친 고객의 시간이 동일
				while (queue.size() > 0 && queue.peek()[0] == temp[0]) {
					temp = queue.poll();
					result += new Long(temp[2]) * new Long(r);
					r += 1;
					arr[temp[1]] = false;
				}
                
                // 계산대의 번호가 작은 곳부터 채워줌
				for (int j = 0; j < k; j++) {
					if (!arr[j]) {
						if (flag) {
							st = new StringTokenizer(bf.readLine());
							i += 1;
							id = Integer.parseInt(st.nextToken());
							w = Integer.parseInt(st.nextToken());
						}
						queue.add(new int[] { w + temp[0], j, id });
						arr[j] = true;
						flag = true;
						if (i == n)
							break;
					}
				}
			}
		}

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			result += new Long(temp[2]) * new Long(r);
			r += 1;
		}
		System.out.println(result);
	}
}

 

Main

변수)
n : 고객 수
k : 계산대 수
queue : [시간, 계산대 번호, 고객의 회원번호] / 시간 오름차순 + 계산대 번호 내림차순 
idx : 계산대 번호
r : 쇼핑몰을 빠져나가는 순서
result : 출력값
arr : 계산대 가능 여부
i : 회원 수 count
flag : 고객의 정보를 더 입력받아야 하는가 확인 여부
id : 고객의 회원번호
w : 고객이 구매한 물건의 수

 

- 고객 수(n)와 계산대 수(k) 입력

- 고객 정보 입력받음

1) 아직 계산대 수만큼 고객이 있지 않다면 queue에 추가

2) 계산대가 꽉 찼다면

: 시간이 제일 작은 고객을 내보냄 (계산이 끝나는 시간이 같은 사람들이 있을 수 있으므로 queue.peek을 통해 확인해서 같이 내보냄)

: 계산대가 비어있는지 확인 후 고객을 계산대로 보냄

---

---