[Python] 백준 11000 강의실 배정

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

11000번: 강의실 배정

 

1. 접근 방법

시작 끝 시간을 기반으로 간단한 그리디라 생각했는데, 문제를 다시 읽고 보니 전체 강의 실수를 확인하는 조금 번거로울 수 있는 문제였다.

이를 해결하기 위해 heap을 활용하여 가장 빨리 끝나는 시간 기준으로 고민했다.

 

2. 풀이 코드

🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/11000/11000.py

📕코드 해설

시작 시간 기준으로 오름차순 정렬하고, heap에는 끝나는 시간을 저장했다.

각 시작시간을 비교하여 끝나는 시간이 더 빠르다면 바꿔서 넣고, 아니라면 새로 추가했다.

마지막으로 heap의 길이를 출력하면 필요한 강의실을 구할 수 있다.

 

3. 생각 정리

이런 문제에서 push-pop을 연속으로 처리하는 경우 pushpop을 활용하는것이 좋다. 이 문제에서 적극적으로 활용하여 코드량도 줄이며 아마도 속도 증가에도 큰 긍정적 영향이 있었으리라 생각한다.