BOJ 17612 쇼핑몰

개요

이 문제는 우선순위 큐를 사용하는 문제지만, 정렬 방법에 대해 이해하고 있어야 하고 무엇보다 문제에서 주어진 요구사항을 동적으로 처리하는것보다 사전에 전처리하여 값을 모두 저장 한뒤 문제 요구사항에 맞게 풀어야 했었습니다. 

처음에는 while 문으로 계속 돌면서 입력 받는대로 동적으로 값을 처리 해주었습니다. 결과적으로 꼬였습니다.

그래서, k개 즉 카운터라고 볼 수 있는 k개에 쇼핑 카트를 모두 대기하는 값을 pq에 담게 되었습니다.

그림

그림을 보게 되면 어쨋든, 상품들이 1초에 하나씩 계산이 될텐데 더 적은 상품에 대해서 카운터에 배정되게 됩니다. 

상품의 개수가 같다면 카운트가 더 적은 애한테 우선 할당하게 되는데 그게 인입하는 과정에서 수행하게 됩니다. 

반대로, 나갈때도 마찬가지로 기본적인 더 적은 상품에 대해 내보내고 만약 같다면 더 큰 계산대에 있는 상품을 먼저 내보내게 됩니다. 

이게 문제에서 요구하는 사항이었습니다. 

그러면 구현에 대해서 생각해보면, 우선순위 큐와 ArrayList 를 사용하여 접근할 수 있습니다. 

 

그림2

우선 최초로 pq에 인입하는 과정을 모두 담게 됩니다. 

그러면 그림 처럼 순서대로 인입을 하게 될것입니다. 만약, 같은 product 의 경우에는 더 작은 카운트 값에 배정되겠습니다. (그림에서는 같은 product는 없다고 가정)

pq에 담을 시 시간 소요는 앞에 대기하고 있는 상품이 있다면 해당 상품이 처리되는 시간까지 더해서 pq에 삽입하게 됩니다.

그리고 pq에 모두 담았으면 하나씩 빼서 ArrayList에 담게 됩니다. 

일종에 아웃에 대한 순서를 만들기 위해서 인입 순서대로 ArrayList에 담게 되고 재정렬을 수행하게 됩니다. 

각각 pq와 ArrayList를 사용한 이유는

1. pq의 경우 Min-heap 혹은 Max-heap에 대해 쉽게 구할 수 있습니다. 

2. ArrayList의 경우 조회나 전체 정렬하는데 있어 비교적 쉽게 구현할 수 있습니다.  

코드

package backjun;
 
import java.util.*;
import java.io.*;
public class BOJ_17612_쇼핑몰 {
 
    static class Node{
        int id;
        int weight;
        int casherId;
        Node(int id, int weight, int casherId){
            this.id=id;
            this.weight=weight;
            this.casherId=casherId;
        }
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        PriorityQueue<Node> pq = new PriorityQueue<>(1, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                // TODO Auto-generated method stub
                if(o1.weight==o2.weight)
                    return o1.casherId-o2.casherId;
                return o1.weight-o2.weight;
            }
        });
        
        ArrayList<Node> al = new ArrayList<>();
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int id = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            if(i<k){
                pq.add(new Node(id, weight, i+1));
            }else {
                pq.add(new Node(id, pq.peek().weight+weight, pq.peek().casherId));
                al.add(pq.peek());
                pq.poll();
            }
        }//end of for loop
        
        while(!pq.isEmpty()) {
            al.add(pq.peek());
            pq.poll();
        }
        
        Collections.sort(al,new Comparator<Node>() {
 
            @Override
            public int compare(Node o1, Node o2) {
                // TODO Auto-generated method stub
                if(o1.weight==o2.weight)
                    return o2.casherId-o1.casherId;
                return o1.weight-o2.weight;
            }
            
        });
        
        long ans = 0;
        int cnt = 1;
        for(int i=0; i<al.size(); i++) {
            ans+=((long)(al.get(i).id)*(cnt++));
        }
        System.out.println(ans);
    }
}