(Python/🥈1)백준 알고리즘 1931번: 회의실 배정

 

문제 바로가기 

백준 알고리즘 회의실 배정

 

문제:

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력:

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력:

 

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

 

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
time = [list(map(int,sys.stdin.readline().rstrip().split(" "))) for i in range(N)]

time.sort(key = lambda x:(x[1],x[0]))
count = 0
idx = 0
for i in time:
    if i[0] >= idx :
        idx = i[1]
        count += 1
print(count)

이 문제는 예전에 프로그래머스에서 풀었던 단속카메라 문제와 거의 유사하다.

아이디어는 좀 쉽지만 구현이 어려웠던것 같다.

 

일단 시간을 끝나는 시간을 기준으로 한다. 빨리 끝날수록 고려할 케이스들이 많기 때문이다

idx는 끝나는 시간을 저장하는것이다.

그래서 [1,4] 로 들어오면 4로 끝나는 시간 이면서 그 다음회의 시작시간이다.

for문으로 돌면서 끝나는 시간과 같거나 크면 또 그 해당인덱스의 끝나는 시간으로 바꿔주면 된다.

 

[1,4]

[1,4] 과 [3,5],[0,6] 은 idx는 4지만 , 시작시간인 3과, 0 과 보다 크므로 제껴지고

[5,7] 은 4보다 큰 시간에 시작하므로 추가되면서 idx는 끝나는 7 로 최신화

이런식으로 쭉 간다.

 

 

https://windy7271.tistory.com/entry/PythonLV3-%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC

(Python/LV3) 단속카메라