[IT/코딩테스트] 99클럽 코테 스터디20일차 TIL + BOJ19598

 

오늘의 문제

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

 

 

뭔가 그리디, 우선순위 큐 문제는 익숙해진 것 같다.

역시 나의 천적은 BFS, DFS,,,, 그거 할때랑 지금이랑 문제 풀 때 기분이 다르다 ㅋㅋㅋㅋ

 

일단 숫자 범위부터 작기도 하고~ 

오늘까지 문제풀이 시간이 적어서 다행이다... 🥹🍀

 

---

나의 첫 번째 풀이 (성공)

아래는 문제를 어떻게 풀 것인가에 대해서 생각한 흐름

 

1. 입력받은 회의들을 (시작 시간, 종료 시간) 기준으로 정렬 -> 먼저 시작하는 회의부터 처리

 

2. 첫번째 회의실의 종료시간을 heap 에 저장 ( 회의실 개수 기본값 1 )

 

3. 현재 회의의 시작 시간이 가장 빨리 끝나는 회의 이후라면, 같은 회의실에서 진행 가능

👉 기존의 회의실을 재사용할 수 있으므로 heapq.heappop(heap)을 통해 종료된 회의 제거

** 회의 종료 시간보다 늦게 시작할 때
times2[i][0] >= heap[0]

 

4. 회의 시간이 겹친다면, 새로운 회의실 필요 ( room +1 )

** 회의 종료 시간보다 전에 시작할 때
times2[i][0] < heap[0]

 

5. 현재 회의 종료 시간 추가

 

 

그렇게 작성한 코드를 파이참에서 실행해보았고, 올바르게 동작하는 것을 확인한 후에 백준 사이트에 입력했다.

그리고 결과는 ..... 

 

 

 

작성 전체 코드

import sys
import heapq

n = int(sys.stdin.readline())
times = []

for _ in range(n):
    times.append(list(map(int, sys.stdin.readline().split())))

times2 = sorted(times)
heap = []
room = 1

heapq.heappush(heap, times2[0][1])
for i in range(1, n):
    if times2[i][0] >= heap[0]:
        heapq.heappop(heap)
    else:
        room+=1
    heapq.heappush(heap, times2[i][1])

print(room)

 

 

이제 빨리 또 개발하러 가자.... 🥹

오늘도 밤샘 예약이다... 

 

그런데 다음주 알고리즘 주제는 뭘까??