[백준 파이썬] 19598 최소 회의실 개수

[백준 파이썬] 19598 최소 회의실 개수

 

문제

n개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다.

각회의는 시작과 끝 나는 시간이 주어진다. 한 회의실에서 동시에 2개의 회의 진행은 불가능하다.

회는 중간에 중단될수 없으며 끝나야지 다음 회의를 진행할 수 있다.

회의 시작 시간은 끝나는 시간보다 항상 작다 

입력

첫줄은 배열의 크기 n

둘째 줄부터 공백사이를 두고 회의 시작 시간과 끝나는 시간이 주어진다.

출력

최소 회의실 개수를 출력한다.

풀이

정답을 넣을 리스트를 만들고 

처음 시작할 때 아무런 조건 없이 회의실을 배정받을 수 있다

그 후부터는 배정받은 회의의 끝나는 시간을 다른 회의들의 시작시간하고 비교하여 그 자리를 대체하거나

새로운 회의실을 배정받는 식으로 문제를 풀 수 있다.

 

처음 코드를 작성할 때에는 정답을 저장할  리스트에는 끝나는 시간만 넣어서 그 끝나는 시간이 가장 낮은 거 하고 다음 회의의 시작 시간하고 비교하면서 코드를 작성하였다

정답에 들어 있는 리스트의 가장 작은 값보다 다음 회의 시간이 크거나 같다면 면 그 가장 작은 값이 들어있는 곳의 인덱스 값을 찾아

그 자리에 다음회의 끝나는 시간 값을 넣고 만약 작다면 정답 리스트에 다음 회의 끝나는 시간값을 넣어서 마지막에

정답 리스트의 길이를 출력하여 답을 출력하는 코드를 작성하였다

시간 초과 코드 

n=int(input())

array=[]

for i in range(n):

    a,b=map(int,input().split())

    array.append([a,b])

array.sort(key=lambda x: (x[0],x[1]))

ans=[]

for x,y in array:

    if len(ans)==0:

        ans.append(y)

    else:

        if min(ans)<=x:

            idx=ans.index(min(ans))

            ans[idx]=y

        else:

            ans.append(y)

print(len(ans))

결과는 시간 초가로 다른 방법을 생각해야 했다 일단 시간초과가 난이유는 아마 인덱스 값을 확인하고 append로 추가하는 부분에서 시간초과가 난 걸로 보인다 

 

값을 넣었을 때 우선순위에 따라 자동적으로 배열의 순서를 조작해 주는 heqpq를 사용하였다

heapq는 이진힙으로 작은 값을 앞으로 배치해 준다

heappush()는 값을 넣는 코드이며 heappop()는 가장 우선순위가 높은 값을 빼내는 코드이다 다른 말로 하면 가장 낮은 값을 빼낸데 

코드

import heapq

n=int(input())

array=[]

for i in range(n):

    a,b=map(int,input().split())

    array.append([a,b])

array.sort(key=lambda x: (x[0],x[1]))

ans=[]

for x,y in array:

    if len(ans)==0:

        heapq.heappush(ans,y)

    else:

        if ans[0]<=x:

            heapq.heappop(ans)

            heapq.heappush(ans,y)

        else:

            heapq.heappush(ans,y)

print(len(ans))