[JAVA] 백준 - 17612 : 쇼핑몰

문제 링크

17612번: 쇼핑몰

 

풀이 ) 우선순위큐

  처음에는 큐를 이용해서 완전탐색을 하는 방식으로 구현하려했지만 이럴 때의 시간복잡도는 O(nk)가 되고 n과 k가 각각 10만 이하이므로 완전탐색으로는 해결할 수 없었다.

 

  계산대를 이용하는 고객을 저장하는 우선순위큐를 만들어서, 끝나는 시간이 빠르고 이용하는 계산대의 번호가 큰 순서대로 우선순위가 높게 만들었다.

 

  손님을 줄세우고 먼저 계산대에 모두 채워 넣는다. (* 이때 계산대의 수에 조심하지 않으면 null pointer exception 발생)

 

  이후 계산이 가장 빨리 끝나는 고객의 시간으로 시간을 갱신한 이후(time = counter.peek().time), 해당 시간에 계산이 끝나는 고객을 모두 제거하고(pollAt(time)) 비어있는 계산대에 손님으로 채운다.(offerAt(time))

  

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int n, k;
    static Queue<Info> customers = new LinkedList<>();	// 고객 줄
    static PriorityQueue<Info> counters = new PriorityQueue<>((o1, o2)->{
        if(o1.time == o2.time)
            return o2.num-o1.num;
        return o1.time-o2.time;
    });		// 끝나는 시간이 짧고, 계산대 번호가 큰 순서대로 제거하는 우선순위큐
    static Stack<Integer> vacancy = new Stack<>();	// 비어있는 계산대
    static long answer;		// 결과
    static int nFinish;		// 계산 끝난 사람 수

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

    static void solve() throws IOException {
        int time = 0;
        for(int i = 0; i < k; ++i){		// 처음 k명 계산대 이용
            if(customers.isEmpty())		// * 주의사항: 계산대수 > 고객수
                break;
            Info customer = customers.poll();
            customer.time = customer.w;
            customer.num = i;
            counters.offer(customer);
        }
        while(!customers.isEmpty()){
            if(!counters.isEmpty())
                time = counters.peek().time;	// 시간 갱신
            pollAt(time);
            offerAt(time);
        }

        while(!counters.isEmpty())	// 줄이 없는 상태에서 계산대 이용중인 고객 계산
            answer += 1L * (++nFinish) * counters.poll().id;

        bw.write(answer+" ");
        bw.flush();
    }

    static void pollAt(int time){	// time 시간에 계산을 마치는 고객 모두 계산대에서 제거
        while(!counters.isEmpty()){
            Info counter = counters.peek();
            if(counter.time == time){	// 가장 빨리 끝나는 고객의 시간이 현재시간이면 제거
                counters.poll();
                vacancy.push(counter.num);	// 비어있는 계산대 추가
                answer += 1L * (++nFinish) * counter.id;	// 정답 추가
            }
            else
                break;
        }
    }

    static void offerAt(int time){	// time 시간에 빈 계산대에 고객 채우기
        while(!customers.isEmpty() && !vacancy.isEmpty()){
            Info customer = customers.poll();
            customer.num = vacancy.pop();	// 비어있는 계산대 이용
            customer.time = time+customer.w;	// 계산대 이용하는 고객의 끝 시간 갱신
            counters.offer(customer);		// 계산대 이용
        }
    }

    static void input() throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            customers.offer(new Info(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
    }

    static class Info{
        int id, w, time, num;
        // id: 고객의 회원번호
        // w: 물건 개수(계산 소요 시간)
        // time: 계산을 마치는 시간
        // num: 이용하는 계산대 번호 

        public Info(int id, int w) {
            this.id = id;
            this.w = w;
        }
    }
}

 

주의 )

• 계산대의 수가 손님보다 많은 경우