[백준] 11000 강의실배정 | Gol5 | 힙? Python

[백준] 11000 강의실배정 | Gol5 | 힙? Python

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

 

구상

• 풀이 1 : 리스트 (시간초과, pypy만 통과)
• 풀이 2 : 힙 (시간초과, pypy만 통과)
  **풀이1, 2 는 동일 로직인데 사용한 자료구조만 다른 코드
• 풀이 3 : 힙
  • 힙을 써서 통과된 게 아니라 로직을 더 효율적으로 개선해서 통과된 것임다
    동일 로직으로 리스트로도 가능할지도?
    그리고 다른 코드들 찾아보니까 더더 효율적인 로직이 있었다. 논리적으로 이해하기에는 내 코드가 쉽고, 대신 덜 효율적

 

[문제 해석]

• 시간대가 겹치는 수업들을 최소한의 강의실에 배치하라
• 답 : 강의실 최소개수
• 시간제한 : 1초

 

구상

• 효율 개선한 로직
  • 수업 시작시각, 종료시각을 시간순으로 정렬하고
  • 강의 시작 시각을 돌며 해당 시작 시각 전에 끝난 강의가 있는지 체크하여 빈강의실+1
  • 빈 강의실이 있다면 그걸 사용하고, 없다면 새로운 강의실+1
• 비효율적인 로직
  • 수업 시작시간, 종료시간을 시간순으로 정렬하고
  • 시간을 흐르게 하면서 각 시간에 빈 강의실이 있다면 그걸 사용하고, 없다면 새로운 강의실을 추가하자
  • 수업이 끝나면 빈강의실+1
• 다른 풀이들 보니까 힙 안쓰고도 구현 가능함

 

트러블 슈팅

• 시간이 등장하는 문제에서 꼭 시각을 하나하나 돌려고 하지 말자. 유의미한 시각만 돌게 생각해볼 것

 

코드 - 힙, 효율 개선된 로직

# v3 : 힙
# TS : 시간이 등장하는 문제에서 꼭 시각을 하나하나 돌려고 하지 말자. 유의미한 시각만 돌게 생각해볼 것

'''
[문제 해석]
- 시간대가 겹치는 수업들을 최소한의 강의실에 배치하라
- 답 : 강의실 최소개수
- 시간제한 : 1초



구상
수업 시작시각, 종료시각을 시간순으로 정렬하고
강의 시작 시각을 돌며 해당 시작 시각 전에 끝난 강의가 있는지 체크하여 빈강의실+1
빈 강의실이 있다면 그걸 사용하고, 없다면 새로운 강의실+1
왜 힙이지? - 오 풀다보니까 알겠음..

근데 다른 풀이들 보니까 힙 안쓰고도 구현 가능함
'''

import heapq
import sys
input = sys.stdin.readline

N = int(input())

start = []
end = []

for _ in range(N) :
    s, e = map(int, input().split())
    start.append(s)
    end.append(e)

#시간순 정렬 - heapq사용해서 최소힙으로 만듦
heapq.heapify(start)
heapq.heapify(end)

#현재 사용중인 & 비어있는 강의실 개수 저장 변수
using = 0
empty = 0

while start : #더 시작할 강의가 남아있을 때까지 반복
    #강의 시작 시각
    t = heapq.heappop(start)

    #시작시각 전에 끝난 강의가 있다면 강의실 반납
    while end and end[0] <= t :
        heapq.heappop(end)
        using -= 1
        empty += 1
    
    #강의실 배정
    if empty :
        empty -= 1
    using += 1

#강의실 최소값 = 빈 강의실 수 + 현재 사용중인(끝나면 비게 될) 강의실 수
print(using + empty)

 

코드 - 힙, 비효율적 로직

# v2 : 힙


'''
[문제 해석]
- 시간대가 겹치는 수업들을 최소한의 강의실에 배치하라
- 답 : 강의실 최소개수
- 시간제한 : 1초



구상
일단 수업을 무조건 배치는 해야 됨
수업 시작시간, 종료시간을 시간순으로 정렬하고
시간을 흐르게 하면서 각 시간에 빈 강의실이 있다면 그걸 사용하고, 없다면 새로운 강의실을 추가하자
수업이 끝나면 빈강의실+1
왜 힙이지? - 오 풀다보니까 알겠음..

=> heapq써도 시간초과
    -> 로직을 더 줄일 수 있을 듯? for문을 시간별로 안돌고
'''

import heapq
import sys
input = sys.stdin.readline

N = int(input())

start = []
end = []

for _ in range(N) :
    s, e = map(int, input().split())
    start.append(s)
    end.append(e)

#시간순 정렬 - heapq사용해서 최소힙으로 만듦
heapq.heapify(start)
heapq.heapify(end)

#현재 사용중인 & 비어있는 강의실 개수 저장 변수
using = 0
empty = 0

#시간을 돌면서 강의실 배정
for t in range(max(start)+1) : #제일 늦게 시작하는 강의의 시작시각까지 반복
    #남은 강의 중 제일 먼저 끝나는 강의가 현재시간과 같으면 계속 확인
    while end and end[0] == t : 
        heapq.heappop(end)
        using -= 1
        empty += 1

    #남은 강의 중 제일 먼저 시작하는 강의가 현재시간과 같으면 계속 확인
    while start and start[0] == t : 
        heapq.heappop(start)
        #빈강의실 있으면 그거줌
        if empty != 0 : 
            empty -= 1
        using += 1

#강의실 최소값 = 빈 강의실 수 + 현재 사용중인(끝나면 비게 될) 강의실 수
print(using + empty)

 

코드 - 리스트, 비효율적 로직

# timeout : 리스트
#           python시간초과, pypy로는 통과!
#           논리는 맞았으나 리스트로는 시간초과가 난다. 힙으로도 해보자


'''
[문제 해석]
- 시간대가 겹치는 수업들을 최소한의 강의실에 배치하라
- 답 : 강의실 최소개수
- 시간제한 : 1초



구상
일단 수업을 무조건 배치는 해야 됨
수업 시작시간, 종료시간을 시간순으로 정렬하고
시간을 흐르게 하면서 각 시간에 빈 강의실이 있다면 그걸 사용하고, 없다면 새로운 강의실을 추가하자
수업이 끝나면 빈강의실+1
왜 힙이지? - 오 풀다보니까 알겠음..
'''

import sys
input = sys.stdin.readline

N = int(input())

start = []
end = []

for _ in range(N) :
    s, e = map(int, input().split())
    start.append(s)
    end.append(e)

#시간순 정렬 - 제일 먼저 시작하는 값이 제일 마지막에 위치. pop하기 쉽게
start.sort(reverse=True) #아 힙쓰면 항상 최솟값뽑을때 heappop으로 해서 편하긴 하겠네..
end.sort(reverse=True)

#현재 사용중인 & 비어있는 강의실 개수 저장 변수
using = 0
empty = 0

#시간을 돌면서 강의실 배정
for t in range(start[0]+1) : #제일 늦게 시작하는 강의의 시작시각까지 반복
    #남은 강의 중 제일 먼저 끝나는 강의가 현재시간과 같으면 계속 확인
    while end and end[-1] == t : 
        end.pop()
        using -= 1
        empty += 1

    #남은 강의 중 제일 먼저 시작하는 강의가 현재시간과 같으면 계속 확인
    while start and start[-1] == t : 
        start.pop()
        #빈강의실 있으면 그거줌
        if empty != 0 : 
            empty -= 1
        using += 1

#강의실 최소값 = 빈 강의실 수 + 현재 사용중인(끝나면 비게 될) 강의실 수
print(using + empty)