[백준 정렬] 강의실 배정

 

파이썬으로 푼 이유는 갑자기 알고리즘을 풀고 싶어서 풀다가 자바스크립트로 입출력하기 귀찮아서이다.

n = int(input())

time = []
for _ in range(n):
  time.append(tuple(map(int, input().split())))

# print(time)

time = sorted(time, key=lambda x: (x[0], x[1]))

# print(time)
cnt = 0
while len(time) > 0:
  start = time[0][0]
  end = time[0][1]
  del time[0]
  for i in range(len(time)):
    if time[i][0] >= end:
      start = time[i][0]
      end = time[i][1]
      del time[i]
      break

  cnt += 1

print(cnt)

 

맞는 풀이라고 생각했다. 하지만 시간초과가 났다. 이제보니 N이 20만까지 있다. 시간초과가 나는게 당연하다.

그러면 어떻게 풀 수 있을까??

 

...고민중....

 

약 8분 경과

 

굳이 이중 반복을 해줄 필요가 없다는 생각이 들었다. while문 밖에서 일단 초기값을 정해주고 for문을 돌아보았다.

ㅇㅇ

 

n = int(input())

time = []
for _ in range(n):
  time.append(tuple(map(int, input().split())))

# print(time)

time = sorted(time, key=lambda x: (x[0], x[1]))

# print(time)
cnt = 0
start = time[0][0]
end = time[0][1]
del time[0]

i = 0
while len(time) > 0:
  if time[i][0] >= end:
    start = time[i][0]
    end = time[i][1]
    del time[i]

    if i==len(time)-1:
      start = time[0][0]
      end = time[0][1]
      del time[0]
    
    continue
  else:
    i+=1
    continue

  cnt += 1

print(cnt)

 

위 코드를 생각없이 구현하다가 count를 셀 코드를 어떻게 둘지 못찾아서 이렇게 단순 반복문을 돌며 count를 세는 걸로는 풀리는 문제가 아니란 것을 알았다.

 

힙 자료구조를 이용해야 한다는 건 문제를 풀기 전에 알고 있었긴 했다. 그러면 힙자료구조를 통해 풀어보자

 

회의실을 힙으로 관리하는게 일반적인 풀이인 것 같다. 굳이 힙인 이유는 비교대상을 최대한 시간이 일찍 끝나는 것으로 정해야 하기 때문이려나

 

import heapq

n = int(input())

time = []
for _ in range(n):
  time.append(tuple(map(int, input().split())))

# print(time)

time = sorted(time, key=lambda x: (x[0], x[1]))

heap = []
heapq.heappush(heap,time[0][1])

for i in range(1, n):
  if time[i][0] < heap[0]:
    heapq.heappush(heap, time[i][1])
  else:
    heapq.heappop(heap)
    heapq.heappush(heap, time[i][1])

print(len(heapq))

 

이렇게 풀었다. 아니 근데 풀고 있는데 repl에서 copilot 비슷한 걸 지원해주는지 내가 어떤 의도를 가지고 코드를 쓰는지 다 파악하고 코드를 추천해준다...ㅋㅋ 현타오네 다음엔 자스로 풀어볼까? 근데 자스면 힙을 직접 구현해야 되는 건가?