Site avatar

☀️ Log

개발과 학습에 대한 생각을 기록하는 공간입니다.

GitHub

17612. 쇼핑몰

9 min read

INFO

1. 문제 이해

핵심 요구사항

  • 목표: 손님이 계산을 완료하고 쇼핑몰을 나오는 순서 구하기 → ()

  • 입력

    • N: 사람 수
      • : 사람 별 id
      • : 사람 별 걸리는 시간(산 물건 수)
    • K: 계산대 수

  • 계산 규칙

    • 계산에 걸리는 시간 = 물건 수(w)
    • 계산대 입장과 퇴장에 걸리는 시간은 없음
    • 순서 기준
      • 입장 시 → 1. 빨리 끝남 / 2. 계산대 번호가 작음
      • 퇴장 시 → 1. 빨리 끝남 / 2. 계산대 번호가 큼

제한 조건

  • 변수 범위 → long
    • 입력
      • 1 ≤ N ≤ 100,000
      • 1 ≤ id ≤ 1,000,000
      • 1 ≤ w ≤ 20
      • 1 ≤ k ≤ 100,000
    • 출력: long 사용해야함
  • 시간: 1초 →
    • 최대 안으로.
  • 메모리: 512MB → 넉넉

2. 사고의 흐름 (Thinking)

  • **✅ 1차 시도: 우선순위 큐 → 가용 계산대 큐(계산대 기준), 계산 중 큐(customer 기준) && 바로바로 결과값 계산

    • 들어갔다가 시간 순서대로 나오는 걸 구하는 문제 → 우선순위큐가 적합
    • heap을 사용한다면 으로 해결 가능 ( = heap 삽입/삭제 → n번 함)
    • ⇒ 시뮬레이션 관점 / 동시 처리 어려움

  • ✅✏️ 2차 시도: 우선순위 큐 → 계산대 큐 하나만 사용 && 사용자별 계산 종료시간을 기록해뒀다가 한번에 정렬

    • 기준이 ‘끝나는 시간’임을 염두에 둔다면 훨씬 간단하게 생각할 수 있음. → like 16235. 나무 재테크
    • 정렬 기준이 여럿인 경우.실시간으로 처리하기 보다는 값을 기록해두고 전체를 확인하여 한번에 처리하는게 안전할 수도 있음
    • ⇒ 스케줄링 관점 / 실시간성이 필요 없어서 미리 계산 후 정렬

3. 풀이 및 코드 (Solution)

방법 1: 우선순위 큐 2개 / 실시간 결과 처리

import java.io.*;
import java.util.*;
 
// Customer 클래스 선언
class Customer implements Comparable<Customer>{
    int id, w;
    Counter c;
 
    public Customer(int id, int w) {
        this.id = id;
        this.w = w;
    }
 
    @Override
    public int compareTo(Customer o) {
        if (this.c.end_time == o.c.end_time) {
            return o.c.id - this.c.id; // 퇴장시에는 큰 수부터
        }
        return this.c.end_time - o.c.end_time;
    }
}
 
class Counter implements Comparable<Counter> {
    int id, end_time = 0;
 
    public Counter(int id) {
        this.id = id;
    }
 
    @Override
    public int compareTo(Counter o) {
        if (this.c.end_time == o.c.end_time) {
            return this.c.id - o.c.id; // 입장시에는 큰 수부터
        }
        return this.c.end_time - o.c.end_time;
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 기본 입력 받기 / 기본 선언(cnt/result)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, k, cnt=1;
        long result=0;
        Customer[] customers;
 
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        k = Integer.parseInt(temp[1]);
 
        // N번 돌면서 customer 생성 / customers 배열에 넣어두기
        customers = new Customer[N+1];
        for (int n=0; n<N; n++) {
            temp = br.readLine().split(" ");
            int id = Integer.parseInt(temp[0]);
            int w = Integer.parseInt(temp[1]);
 
            customers[n] = new Customer(id, w);
        }
 
        // 우선순위큐 선언
        // 계산대 (1-k)
        PriorityQueue<Counter> counters = new PriorityQueue<>();
        for (int id=1; id<=k; id++) {
            counters.offer(new Counter(id));
        }
        // 계산중 (빈 배열) -> 1번 손님 삽입
        PriorityQueue<Customer> calculating = new PriorityQueue<>();
 
 
        // customer 배열 돌면서
        for (int n=0; n<N; n++) {
            Customer now = customers[n];
            int prev_time = -1;
            while (counters.isEmpty()|| (!calculating.isEmpty() && prev_time == calculating.peek().c.end_time)){
                Customer customer = calculating.poll();
                result += (long) customer.id * cnt++;
                counters.offer(customer.c);
                prev_time = customer.c.end_time;
            }
            Counter counter = counters.poll();
            now.c = counter;
            counter.end_time += now.w;
            calculating.offer(now);
        }
 
        while (!calculating.isEmpty()) {
            Customer out = calculating.poll();
            result += (long) out.id * cnt;
            cnt++;
        }
 
        System.out.println(result);
    }
}

  • 단순하게

    • 입장시에 손님에게 할당할 가용계산대를 고르는 큐 하나
    • 계산이 빨리 끝나는(+계산대 번호가 큰) 순서대로 추출할 큐 하나
    • 이렇게 2개의 우선순위 큐 생성

  • 사용자 배열을 0~N-1까지 돌면서,

    • 가용 계산대 큐에 계산대가 있으면
      • id 작은 순서로 계산대 할당 후
      • 해당 사용자를 계산 중 큐에 넣음
    • 없으면
      • 가장 빨리 계산이 끝나는 모든 계산대를(여러개일 수 있음) 빼서 가용 계산대 큐에 넣음
      • 이때 계산을 마친 사용자에 대해서 결과값 계산
      • 이후 위의 연산 진행

  • ⇒ 시간 기반 연산

  • 시간복잡도:

    • 요소 수가 k인 힙 시간 복잡도: log k
    • 힙에 N번 삽입/삭제함

방법2: 우선순위 큐 1개/모아서 결과값 처리

import java.io.*;  
import java.util.*;  
  
class Customer implements Comparable<Customer>{  
    int id, end_time, counter;  
  
    public Customer(int id, int end_time, int counter) {  
        this.id = id;  
        this.end_time = end_time;  
        this.counter = counter;  
    }  
  
    @Override  
    public int compareTo(Customer o) {  
        if (this.end_time == o.end_time) {  
            return o.counter - this.counter; // 퇴장시에는 큰 수부터  
        }  
        return this.end_time - o.end_time;  
    }  
}  
  
class Counter implements Comparable<Counter> {  
    int id, end_time = 0, user;  
//    Customer user;  
  
    public Counter(int id) {  
        this.id = id;  
    }  
  
    @Override  
    public int compareTo(Counter o) {  
        if (this.end_time == o.end_time) {  
            return this.id - o.id; // 입장시에는 작은 수부터  
        }  
        return this.end_time - o.end_time;  
    }  
}  
  
public class BOJ17612_쇼핑몰 {  
    public static void main(String[] args) throws IOException {  
        // 기본 입력 받기 / 기본 선언(cnt/result)  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int N, k, cnt=1;  
        long result=0;  
        PriorityQueue<Counter> calculating =new PriorityQueue<>();  
        ArrayList<Customer> customers = new ArrayList<>();  
  
        String[] temp = br.readLine().split(" ");  
        N = Integer.parseInt(temp[0]);  
        k = Integer.parseInt(temp[1]);  
  
        // 계산대 세팅  
        for (int id=1; id<=k; id++) {  
            calculating.offer(new Counter(id));  
        }  
  
        // N번 돌면서 계산 돌리기  
        for (int n=0; n<N; n++) {  
            temp = br.readLine().split(" ");  
            int id = Integer.parseInt(temp[0]);  
            int w = Integer.parseInt(temp[1]);  
  
            Counter counter = calculating.poll();  
  
            counter.user = id;  
            counter.end_time += w;  
            calculating.offer(counter);  
            customers.add(new Customer(counter.user, counter.end_time, counter.id));  
        }  
  
        Collections.sort(customers);  
        for (Customer c : customers) {  
            result += (long) c.id*cnt;  
            cnt++;  
        }  
        System.out.println(result);  
    }  
}

  • 현재 계산이 끝나는 시간 정보를 가진 계산대 우선순위 큐를 생성

    • 가장 빨리 끝나면서, 가장 번호가 작은 계산대를 기준으로 정렬

  • 차례대로 사용자가 쓸 계산대를 추출

  • 사용자의 계산시간을 계산대의 끝나는 시간에 더해서 다시 우선순위 큐에 넣음

  • 동시에 사용자에게 해당 사용자의 계산이 끝나는 시간과 사용 계산대 정보를 담아 사용자 배열에 넣음

  • 이 과정을 반복

  • 반복 후, 사용자 배열을 시간/큰 계산대id에 따라 정렬하여 결과값 출력

  • 시간 복잡도:

    • O(N log N): N개를 정렬
    • O(N log k)
      • 요소 수가 k인 힙 시간 복잡도: log k
      • 힙에 N번 삽입/삭제함

4. 회고 (Retrospective)

  • 순서가 중요한 경우 실시간으로 결과값을 처리하려면 좀더 엄밀하게 코드를 짜야하는 어려움이 있다는 것을 깨달음. → like 동시성 처리
  • 저번의 16235. 나무 재테크처럼 기준을 ‘필수적’인 것으로 한정하고, 그것에만 집중해서 자료구조를 만드는게 중요한데 어렵다. DP 기준잡는게 처음에 어려웠던 것과 비슷한 느낌임.
  • 처음에 방법1로 문제를 풀고, 오답이 떠서 포기하고 AI의 도움을 받아 방법2로 출었는데 문제 정리하면서 방법1도 잘하면 가능할 것같아서 되더라. 내 풀이를 내가 스스로 객관적으로 따져볼 수 있는 힘을 길러야할 것같다.

Computer PS