백준[17612] 쇼핑몰 (Java, Python3)

자료 구조를 만들어 정렬하거나 관찰을 통해서 풀 수 있는 문제
추가시간이 없기 때문에, 10^7 내에 끝내야 한다.

완전 탐색

매초 각 계산대의 물건 카운팅을 1씩 감소시키면서 0이 된 계산대엔 새로운 대기자를 넣는다.
시간 복잡도 계산을 하면서 헷갈렸던 게 고객은 큐로 관리하고, 계산대만 루프를 통해 확인하는 식이기 때문에
O(KW)로 완전 탐색이 가능하다 생각했지만 골 2란 점이 계속 신경 쓰였다.
그래서 조금 최적화하는 방향으로 갔다.

완전 탐색 최적화

계산대를 탐색하는 빈도를 줄이는 방향으로 갔다.

1. 현재 계산대에 물건이 가장 적은 값을 찾는다.
2. 모든 계산대에 그 값만큼 빼준다.
3. 모든 계산대의 물건값이 0이면서 대기 큐가 빌 때까지 반복한다.

우선순위 큐

태그를 확인하니 우선순위 큐 문제길래, 여기에 맞춰서도 풀어봤다.
개인적으로 정렬이 필요한 자료구조 문제의 경우 자바가 편하기 때문에 자바로 작성했다.
우선순위 큐를 2개 사용하는데, 그 이유는 들어오는 기준, 나가는 기준을 서로 다르게 해야 하기 때문이다.

1. 현재 계산대에 대한 우선순위 큐, 나가는 고객에 대한 우선순위 큐를 만든다.
2. 계산대의 우선순위 큐는 무게별로 오름차순, 같다면 계산대 번호별 오름차순으로 정렬한다.
3. 처음 K 개의 고객 데이터는 계산대 큐에 넣지만, 그 이후의 고객의 물건값은 계산대 큐의 상단의 무게와 합한 뒤, 계산대 큐의 상단을 pop 해 나가는 고객 큐에 넣는다.
4. 나가는 고객의 큐는 무게별로 오름차순, 계산대 번호별 내림차순으로 정렬한다.
5. 나가는 고객의 큐를 계속 pop 하면서 id를 계산한다.

자바 코드

import java.io.*;
import java.util.*;

class Main {

    static long N, K;
    static long answer = 0, answerI = 1;
    static PriorityQueue<Calc> calcQ = new PriorityQueue<>();
    // 큐 하나로 관리하면 둘 이상의 계산대에서 빠져나갈 때 계산대 번호가 높은 곳부터 들어가게 됨
    static PriorityQueue<Out> outQ = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int a, b;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            if(i < K) {
                calcQ.add(new Calc(i + 1, a, b));
            }
            else {
                Calc top = calcQ.poll();
                calcQ.add(new Calc(top.index, a, b + top.weight));
                outQ.add(new Out(top.index, top.id, top.weight));
            }
        }
    }

    private static void solve() {
        while (!calcQ.isEmpty()) {
            Calc top = calcQ.poll();
            outQ.add(new Out(top.index, top.id, top.weight));
        }
        printQ();
    }

    private static void printQ() {
        while (!outQ.isEmpty()) {
            Out top = outQ.poll();
//            System.out.println(top.index + ", " + top.id + ", " + top.weight);
            answer += answerI * (long)top.id;
            answerI++;
        }
    }


    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.flush();
    }
}

class Calc implements Comparable<Calc> {
    int index;
    int id;
    int weight;

    public Calc(int index, int id, int weight) {
        this.index = index;
        this.id = id;
        this.weight = weight;
    }

    @Override
    public int compareTo(Calc c) {
        if(weight == c.weight) {
            return index - c.index;
        }
        return weight - c.weight;
    }
}

class Out implements Comparable<Out> {
    int index;
    int id;
    int weight;

    public Out(int index, int id, int weight) {
        this.index = index;
        this.id = id;
        this.weight = weight;
    }

    @Override
    public int compareTo(Out o) {
        if(weight == o.weight) {
            return o.index - index;
        }
        return weight- o.weight;
    }
}

파이썬 코드

from collections import deque

N, K = map(int, input().split())
waitQ = deque()
for _ in range(N):
    a, b = map(int, input().split())
    waitQ.append((a, b))

calc = [[0 for _ in range(2)] for _ in range(K)]
ans, ansI = 0, 1
while True:
    MIN = float("inf")
    flag = True
    for i in range(K):
        if calc[i][1] == 0 and waitQ:
            calc[i][0], calc[i][1] = waitQ.popleft()
        if calc[i][1] > 0:
            MIN = min(MIN, calc[i][1])
    for i in range(K - 1, -1, -1):
        if calc[i][1] != 0 and calc[i][1] - MIN == 0:
            ans += ansI * calc[i][0]
            ansI += 1
            calc[i][0] = 0
        calc[i][1] -= MIN
        if calc[i][1] > 0 or waitQ:
            flag = False
    if flag:
        break
print(ans)