[BaekJoon] 17612 쇼핑몰 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, k;
    static int[][] customers;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        k = scanner.nextInt();
        customers = new int[N][2];

        for(int idx = 0; idx < N; idx++) {
            int id = scanner.nextInt(), time = scanner.nextInt();

            customers[idx][0] = id; customers[idx][1] = time;
        }
    }

    static void solution() {
        int index = 0, time = 0;
        PriorityQueue<Customer> queue = new PriorityQueue<>();
        List<Integer> orders = new ArrayList<>();

        // init
        for(int idx = 1; idx <= k && index < N; idx++) {
            queue.offer(new Customer(customers[index][0], customers[index][1], idx));
            index++;
        }

        while(!queue.isEmpty()) {
            PriorityQueue<Customer> exitCustomers = new PriorityQueue<>(new Comparator<Customer>() {
                @Override
                public int compare(Customer c1, Customer c2) {
                    return c2.counterNum - c1.counterNum;
                }
            });
            PriorityQueue<Integer> counterNums = new PriorityQueue<>();
            Customer cur = queue.poll();
            counterNums.offer(cur.counterNum);
            exitCustomers.offer(cur);
            int curTime = cur.time;
            while(!queue.isEmpty() && queue.peek().time <= curTime) {
                Customer customer = queue.poll();
                exitCustomers.offer(customer);
                counterNums.offer(customer.counterNum);
            }

            while(!exitCustomers.isEmpty()) orders.add(exitCustomers.poll().id);

            while(queue.size() < k && index < N) {
                queue.offer(new Customer(customers[index][0], curTime + customers[index][1], counterNums.poll()));
                index++;
            }
        }

        long answer = 0;
        for(int idx = 1; idx <= orders.size(); idx++)
            answer += (long)idx * orders.get(idx - 1);

        System.out.println(answer);
    }

    static class Customer implements Comparable<Customer> {
        int id, time, counterNum;

        public Customer(int id, int time, int counterNum) {
            this.id = id;
            this.time = time;
            this.counterNum = counterNum;
        }

        @Override
        public int compareTo(Customer c) {
            return time - c.time;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 고객을 나타낼 Customer 클래스를 정의합니다.
  • 고객의 회원번호를 나타내는 id, 해당 고객이 쇼핑몰을 빠져나오는 시간을 나타내는 time, 해당 고객이 들어간 계산대의 번호를 나타내는 counterNum을 멤버 변수로 가집니다.
  • 우선순위 큐에 Customer 객체들을 넣을 것인데, 이 때 쇼핑몰을 빠져나오는 시간의 오름차순으로 정렬되도록 Comparable 인터페이스를 구현합니다.
• 우선순위 큐 queue를 하나 생성하고, 주어진 고객 순서대로 k명을 queue에 담습니다.
• queue에서 고객 한 명을 빼고 현재 들어갈 수 있는 계산대의 번호들을 나타내는 우선순위 큐 counterNums와 현재 나갈 수 있는 고객들을 나타내는 우선순위 큐 exitCustomers를 생성합니다.
• queue에서 빼낸 고객은 나갈 수 있는 고객이므로 exitCustomers에 넣고, 해당 고객의 계산대가 비워질 것이므로 해당 고객의 계산대 번호를 counterNums에 넣습니다.
• queue에서 빼낸 고객이 쇼핑몰을 빠져나오는 시간을 curTime이라고 할 때, curTime보다 쇼핑몰을 빠져나가는 시간이 작거나 같은 고객들을 queue에서 빼내고 이들을 exitCustomers에 넣고 해당 고객들의 계산대가 비워질 것이므로 해당 고객들의 계산대 번호를 counterNums에 넣습니다.
• exitCustomers에 있는 고객들의 회원번호를 정렬 순서에 맞게 쇼핑몰을 빠져나가는 순서를 나타내는 orders라는 List에 넣고 counterNums에 있는 계산대의 번호들에 고객들을 queue에서 하나씩 빼면서 배치합니다.
• 위 작업을 queue가 비워질 때까지 진행합니다.
• 이후에 orders에 있는 순서대로 값을 계산하여 출력합니다.