BOJ - 싸지방에 간 준하 12764번 (JAVA)

❓ 문제 - 백준 싸지방에 간 준하 12764번 - JAVA 풀이법

 

출처 

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

12764번: 싸지방에 간 준하

 

 

📝 문제해결법

1. 문제 해석

• 각 사람의 컴퓨터의 시작 시간과 종료시간에 따라 비어있는 자리 중 가장 작은 자리에 앉게 된다.
• 즉, 한 사용자가 이용할 시작 시간에 현재 비어 있는 자리 중 번호가 가장 작은 자리에 앉는다.
• 따라서 사람들이 싸지방을 이용할 수 있는 컴퓨터의 최소 갯수와 각 자리별로 몇 명의 사람이 앉았는가를 구하면 된다.

2. 해결 방법

• 우선 사람들의 시작시간이 작은 것을 기준으로, 시작시간이 같다면 종료시간이 작은 것을 기준으로 정렬을 수행한다.
• 우선순위 큐 2개를 선언하여 pq에는 현재 활성화된 방의 종료시간과, 방의 인덱스를 넣고 방의 종료시간을 기준으로 오름차순 정렬하게 저장되도록 한다. 그리고 idx 우선순위 큐에는 한 사용자의 시작시간을 기준으로 방의 종료시간이 끝난, 즉 비활성화된 방의 인덱스를 넣는다.
• 한 사용자씩 한 사용자의 시작시간을 기준으로 방의 종료시간이 끝난 방을 pq에서 poll 하면서 비활성화된 방의 인덱스를 idx 우선순위 큐에 넣는다. -> 우선순위 큐를 두 개를 활용하는 이유는 중간에 비활성화된 방이 여러개 있으면 사용자는 비어 있는 자리 중에 번호가 가장 작은 자리에 먼저 앉기 때문이다.
• 현재 비어있는 방중에 앉을 수 있는 방이 있다면 그 방의 인덱스에 사용했던 사용자의 수를 1증가 시켜주고 pq에 그 방을 사용할 사용자의 종료시간과 방의 인덱스 번호를 다시 넣는다.
• 현재 앉을 수 있는 방이 없다면 방의 갯수(cnt)를 1증가 시켜주고 현재 그 방을 사용하려는 사용자의 종료시간과 방의 인덱스를 pq에 넣어준다.
• 현재까지 방이 생성된 갯수(cnt)와 room을 통해 각 방을 사용했던 사용자의 수를 기준에 맞춰 출력해준다.

 

 

3. 삽질 & 느낀점

1) 우선순위 큐로 사용자의 정보를 넣고, 각 방에 대한 정보들을 room 2차원 배열을 통해 현재 방의 종료시간과 방을 사용했던 사용자 수를 관리하며 순서대로 방을 접근해 비어있는지 안 비어있는지를 체크했다. -> 시간 초과 발생

• N의 범위가 100,000 라서 잘못하면 한 사용자마다 계속 방을 만들면 나중에 거의 N^2의 배열 접근을 할 수 있어 시간초가가 발생했다.
• 여기서 우선순위 큐를 조금 더 활용하는 방법을 고민하기 시작했다.

2) 우선순위 큐를 하나 사용하고 그곳에 방의 종료시간과 인덱스 번호를 같이 저장했다. 그리고 사용자에 대한 정보를 list에 넣고 시작 시간이 작은, 시작시간이 같다면 종료시간이 작은 순으로 오름차순 정렬해서 사용자에 대해 접근했다. -> 풀이 오류

• 방에 대한 정보를 종료시간이 작은 순서대로 우선순위 큐에 저장했는데 중간에 테스트를 돌렸을 때 잘못된 값이 나왔다.
• 알고보니 문제의 조건인 비어 있는 방이 여러개 있을 때 사용자는 방의 인덱스가 작은 방을 사용하기 때문에 우선순위 큐는 방의 종료시간을 기준으로 되어 있어서 문제 조건에 부합하지 않은 풀이였다.
• 우선순위 큐를 문제의 조건에도 맞고, 시간초과 나지 않게 어떻게 해결할 수 있을까 고민하였고 다른 사람의 풀이를 참조하였는데 다들 우선순위 큐를 2개 활용하여 방에 대한정보와 비어있는 방에 대한 인덱스를 같이 관리하였다. 따라서 해당 로직들을 참고해서 다시 구현해보았고 문제가 해결되었다..!
• 시간 초과는 내가 사용하는 알고리즘, 자료구조의 전략이 옳바른가 다시 생각해보아야 하며, 풀이 오류는 문제의 조건을 다시 살피면서 조건이 나의 구현에 반영되었는가 고민해봐야겠다고 느꼈다.

 

 

 

 

💻 소스코드 

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

public class Main{
    public static class Node implements Comparable<Node>{
        int start;
        int end;
        public Node(int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Node o){
            if(this.start == o.start){
                return this.end - o.end;
            }
            return this.start - o.start;
        }
    }

    public static class PQNode implements Comparable<PQNode>{
        int end;
        int idx;
        public PQNode(int end, int idx){
            this.end = end;
            this.idx = idx;
        }


        @Override
        public int compareTo(PQNode o) {
            return this.end - o.end;
        }
    }


    public static ArrayList<Node> list;
    public static int[] room = new int[100001];
    public static int n;
    public static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>();

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            list.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Collections.sort(list);
        PriorityQueue<PQNode> pq = new PriorityQueue<>();
        PriorityQueue<Integer> idx = new PriorityQueue<>();

        for (Node node:list){

            while (!pq.isEmpty() && pq.peek().end < node.start){
                idx.add(pq.poll().idx);
            }


            if(!idx.isEmpty()){
                Integer i = idx.poll();
                room[i] += 1;
                pq.add(new PQNode(node.end, i));
            } else {
                cnt++;
                room[cnt] += 1;
                pq.add(new PQNode(node.end, cnt));
            }



        }

        System.out.println(cnt);
        for(int i=1;i<=cnt;i++){
            System.out.print(room[i]+" ");
        }

    }
}