[BOJ/JAVA] 12764번: 싸지방에 간 준하

12764번: 싸지방에 간 준하

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

https://www.acmicpc.net/problem/12764

키워드

• 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙

• 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수

• 자리별로 몇 명의 사람이 사용했는가

---

구현

중요한 것은 우선순위 큐를 이용하여 가장 시간이 짧은 자리를 찾아가면 안된다는 것이다.

예외가 발생하는 경우

현재 시각이 5일 때, 우선순위 큐의 조건을 따른다면, 2번 자리를 찾아갈 것이다. 하지만 조건중에서 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙 을 만족시키지 못하므로 다른 접근 방법이 필요하다.

현재 시각에 이용할 수 있는 좌석을 좌석 번호의 오름차순으로 우선순위 큐(selectedQueue)를 만든다.

기본적인 시작시간, 종료시간은 시작시간 오름차순으로 정렬한다.

• static class Computer
  • static int globalIndex
    • 전체 컴퓨터의 갯수를 저장한다.
  • int endTime
    • 컴퓨터 이용 종료 시각을 저장한다.
  • int index
    • 컴퓨터 번호를 저장한다.

• computerQueue
  • 이용할 수 있는지 체크하는 우선순위 큐이다.
  • 이용하고 있는 사람이 끝나는 시각의 오름차순으로 정렬한다.

• selectedQueue
  • 이용할 수 있는 컴퓨터 우선순위 큐이다.
  • 컴퓨터 번호의 오름차순으로 정렬한다.

• 2개의 우선순위 큐를 이용하여 저글링하듯이 동작시킨다.

1. computerQueue에서 현재 인덱스의 사람이 이용할 수 있는 좌석을 전부 찾는다.
   • 찾은 좌석은 selectedQueue에 삽입한다.

2. selectedQueue가 없으면 새로운 컴퓨터를 설치한다.

3. selectedQueue에서 컴퓨터 번호가 가장 작은 좌석을 찾는다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class java_12764 {
    static int N;
    static List<Person> personList;

    static class Person implements Comparable<Person> {
        int startTime;
        int endTime;

        public Person(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Person o) {
            return this.startTime - o.startTime;
        }
    }

    static class Computer implements Comparable<Computer> {
        static int globalIndex = 0;
        int endTime;
        int index;

        @Override
        public int compareTo(Computer o) {
            // 끝나는 시간 대비
            // 인덱스가 작은 것 우선

            return endTime - o.endTime;
        }

        public Computer(int endTime) {
            this.endTime = endTime;
            this.index = globalIndex++;

        }

    }

    static int solution() {
        int result = 0;

        List<Integer> countList = new ArrayList<>();

        Collections.sort(personList);

        PriorityQueue<Computer> computerQueue = new PriorityQueue<>();
        PriorityQueue<Computer> selectedQueue = new PriorityQueue<>(
                (o1, o2) -> ((Computer) o1).index - ((Computer) o2).index);

        computerQueue.add(new Computer(0));
        countList.add(0);

        for (int i = 0; i < N; i++) {
            Person person = personList.get(i);

            // 기존 컴퓨터에 추가
            while (!computerQueue.isEmpty()) {
                Computer selectedComputer = computerQueue.peek();
                if (!(selectedComputer.endTime > person.startTime)) {
                    selectedQueue.add(computerQueue.poll());
                    continue;
                }
                break;
            }

            if (!selectedQueue.isEmpty()) {
                Computer selectedComputer = selectedQueue.poll();
                selectedComputer.endTime = person.endTime;
                computerQueue.add(selectedComputer);
                countList.set(selectedComputer.index, countList.get(selectedComputer.index) + 1);
                continue;
            }

            countList.add(1);
            computerQueue.add(new Computer(person.endTime));
        }


        System.out.println(countList.size());

        for (int i = 0; i < countList.size(); i++) {
            System.out.print(countList.get(i) + " ");
        }
        System.out.println();

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        personList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());

            Person person = new Person(startTime, endTime);

            personList.add(person);

        }
        solution();

        br.close();
    }
}

---

Uploaded by N2T