[자바] 백준 12764 - 싸지방에 간 준하 (java)

 문제 : boj12764

---

 

필요 알고리즘 개념

• 시뮬레이션, 구현, 우선순위 큐
  
  • 문제에서 제시된대로 시뮬레이션을 구현해주면 된다. 이 문제를 구현할 때 효율적이라 생각한게 우선순위 큐 이므로 우선순위큐도 사용했다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  뭔가 알고리즘적으로 풀이해나가야할 것 같이 생겼는데, 실은 문제에 나온 말 대로 구현만 해주면 풀 수 있다. 다만 쌩구현 문제라고 보기엔 생각이 좀 필요하다.

 

  문제를 보고 구현해줘야하는걸 생각해보자.

1. 당연히 시작 시각 P 순서대로 들어올것이다.

-> 처음 입력받은 N개의 데이터는 P를 기준으로 오름차순 정렬하자.

 

2. 들어올 때, 비어있는 자리 중에서 가장 작은 자리에 앉는다.

-> 우선 비어있는지를 알 수 있어야 한다. 이건 들어온 사람의 P보다, 이미 앉아있던 사람들의 Q가 더 작다면 (같은 경우는 없다는 조건이 있으므로 신경안써도 됨) 비어있다고 보면 된다.

그렇게 비어있는 자리 중 가장 작은 번호를 또 알 수 있어야한다.

 

 

  이하 코드에서 arr은 입력받은 사람들 데이터이다. rooms는 현재 보고 있는 사람의 P를 기준으로, 아직 싸지방에 남아있는 사람들이다. candidates는 비어있다고 판단해도 되는 사람들이다. 별 생각없이 roomCnt나 roomNo라고 썼는데, 해설 쓰면서 보니 방은 하나고 자리가 여러개였다. 아무튼 로직 이해에는 문제가 안될꺼라 생각한다.

Collections.sort(arr, (o1, o2) -> o1.p-o2.p);
//처음 입력받은 N개의 데이터는 P를 기준으로 오름차순 정렬

PriorityQueue<Node> rooms = new PriorityQueue<>((o1, o2) -> o1.q-o2.q);
//아직 남아있는 사람들은 Q를 기준으로 오름차순 정렬 (아래서 cur.P보다 작은 Q를 내보내기 쉽게)

PriorityQueue<Node> candidates = new PriorityQueue<>((o1, o2) -> o1.room-o2.room);
//내보내도 되는사람들은 가장 방번호가 작은 사람부터 내보내야 하므로 방번호 기준 오름차순

int[] roomCnt = new int[n];

int roomNo = 0;
for (Node cur : arr) {
    while (!rooms.isEmpty() && rooms.peek().q < cur.p)
        candidates.add(rooms.poll());
    // 현재(cur)사람의 P보다 Q가 작은 사람들은 candidates로 보낸다.
    
    int selectedRoomNo = candidates.isEmpty() ? roomNo++ : candidates.poll().room;
    // candidates가 비었다는 말은 빈자리가 없단 얘기이므로, 차선책을로 방 번호를 높힌다.
    // candidates가 비어있지 않다면, 가장 방 번호가 작은곳에 앉은사람 자리에 앉는다.
    
    roomCnt[selectedRoomNo]++;
    cur.room = selectedRoomNo;
    rooms.add(cur);
}

 

 

---

 

코드 : github

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

class Node {
    int p, q, room;
    public Node(int p, int q) {
        this.p = p;
        this.q = q;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<Node> arr = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            arr.add(new Node(p, q));
        }

        Collections.sort(arr, (o1, o2) -> o1.p-o2.p);

        PriorityQueue<Node> rooms = new PriorityQueue<>((o1, o2) -> o1.q-o2.q);
        PriorityQueue<Node> candidates = new PriorityQueue<>((o1, o2) -> o1.room-o2.room);
        int[] roomCnt = new int[n];

        int roomNo = 0;
        for (Node cur : arr) {
            while (!rooms.isEmpty() && rooms.peek().q < cur.p)
                candidates.add(rooms.poll());
            int selectedRoomNo = candidates.isEmpty() ? roomNo++ : candidates.poll().room;
            roomCnt[selectedRoomNo]++;
            cur.room = selectedRoomNo;
            rooms.add(cur);
        }

        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for (int i = 0; i < n && roomCnt[i] != 0; i++, cnt++) {
            sb.append(roomCnt[i]).append(' ');
        }
        System.out.println(cnt);
        System.out.println(sb);
    }
}