[C#] 백준 19598번 최소 회의실 개수 (우선순위큐)

[ 문제 ]

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

 

[ 코드 ]

1. 내 코드

using System;
using System.Collections.Generic;
using System.IO;

public class Program
{
    static int N;
    static PriorityQueue<Time, int> pq;

    public static void Main(string[] args)
    {
        N = int.Parse(Console.ReadLine());
        pq = new PriorityQueue<Time, int>(Comparer<int>.Default);

        for (int i = 0; i < N; i++)
        {
            string[] input = Console.ReadLine().Split();
            // 시작 시간은 isStart를 true로, 종료 시간은 false
            pq.Enqueue(new Time(int.Parse(input[0]), true), int.Parse(input[0]));  // 시작시간
            pq.Enqueue(new Time(int.Parse(input[1]), false), int.Parse(input[1])); // 종료시간
        }

        int cnt = 0; // 회의실 개수
        int answer = 0; // 최대값

		// 큐에서 Time 객체를 하나씩 꺼내어 시작 시간 = cnt 증가, 종료 시간 = cnt 감소
        // cnt가 증가할 때마다 answer를 갱신하여 최대 회의실 개수를 추적합니다.
        while (pq.Count > 0)
        {
            Time t = pq.Dequeue();

            if (t.isStart)
            {
                cnt++;
                answer = Math.Max(cnt, answer);
            }
            else
            {
                cnt--;
            }
        }

        Console.Write(answer);
    }

    public class Time : IComparable<Time>
    {
        public int time;
        public bool isStart;

        public Time(int time, bool isStart)
        {
            this.time = time;
            this.isStart = isStart;
        }

        public int CompareTo(Time other)
        {
        //  시간 값을 기준으로 오름차순 정렬
            return this.time - other.time;
        }
    }
}

 

2. 다른 사람 코드

namespace ConsoleApp1
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            StreamReader input = new StreamReader(
                new BufferedStream(Console.OpenStandardInput()));
            StreamWriter output = new StreamWriter(
                new BufferedStream(Console.OpenStandardOutput()));
            int n = int.Parse(input.ReadLine());
            PriorityQueue<int, int> pq = new();
            List<(int, int)> c = new();
            for (int i = 0; i < n; i++)
            {
                int[] temp = Array.ConvertAll(input.ReadLine().Split(' '), int.Parse);
                c.Add((temp[0], temp[1]));
            }
            c.Sort();
            pq.Enqueue(c[0].Item2, c[0].Item2);
            for (int i = 1; i < c.Count; i++)
            {
                if (c[i].Item1 < pq.Peek())
                {
                    pq.Enqueue(c[i].Item2, c[i].Item2);
                }
                else
                {
                    pq.Dequeue();
                    pq.Enqueue(c[i].Item2, c[i].Item2);
                }
            }

            output.Write(pq.Count);

            input.Close();
            output.Close();
        }
    }
}

 

ㅜㅜ 아나 도대체 테스트 케이스는 맞는데 안되는 이유가 뭘까...

그래서 C#은 없길래 다른 언어로 푼 분들꺼 기반으로 해서 냈다.. 흑

이번문제는 다른 언어로 푼 분들꺼 안봤으면 계속 틀리게 냈을 것 같다..... 우선순위큐라는 자료형을 처음봐서 이번에 괘 공부가 됐다.

 

우선순위큐 PriorityQueue라는 개념은 공부겸 가져왔다.

>> 참고 문서

PriorityQueue<TElement,TPriority> 클래스 (System.Collections.Generic)

 

 

[ 실행화면 ]

case: 1

case: 2

 

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/19598