[BOJ_11000] 강의실 배정

 

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

11000번: 강의실 배정

 

✅ 내 풀이(Success) :

 

🧐 Review:

 알고리즘 분류를 확인하지 않았다면 내가 '우선순위 큐'를 이용해서 로직을 생각해봤을까? 아닐 것 같다. 자료구조를 다시 한번 복습해야겠다.

 

문제를 풀고 나서 내가 작성한 코드는 시작 시간과 종료 시간 모두 고려해서 정렬했지만, 구글링을 통해 찾은 코드는 보통 시작 시간을 기준으로만 정렬을 했다. 그래서인지 내 코드에서 readline을 이용해서 입력을 빠르게 받지 않았을 때, 로직에는 이상이 없지만 80% 넘어서 '시간 초과'가 발생하는 것을 확인했다. 어떻게 하면 시간을 더 줄일 수 있을지 생각해보다 입력을 빠르게 받는다면 어떨까라는 생각이 들었고, readline으로 코드를 변경하니 매우 빠르게 통과하는 것을 확인할 수 있었다.

 

🚩 Idea:

 - 입력 값의 크기 n의 최댓값이 200,000으로 매우 크다. for 반복문이 중첩되면 시간 초과가 발생한 것 같다.

 - 중첩된 반복문 없이 로직을 짜봐야겠는데 자료구조는 어떤 것을 사용해야 할까? 감이 오질 않아서 '알고리즘 분류'에서 힌트를 얻었다.

 - 우선순위 큐(= 힙)을 사용하는 로직을 생각해보자.