[백준 1931번] 회의실 배정 - 파이썬

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

💡문제 분석 요약

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

💡알고리즘 설계

입력받은 값을 정렬해야하는 문제이다. 여기서 주의할 점이 있는데, 빨리 시작하는 순서가 아니라 빨리 끝나는 순서대로 리스트를 정렬하고 회의를 해야 더 많은 회의를 할 수 있다. 또한 회의가 끝나자마자 바로 시작할 수 있으므로 회의의 끝나는 시간과 시작하는 시간을 비교할 때 시간이 같은 경우도 처리해야한다 (>=)

💡코드

import sys
input = sys.stdin.readline

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

meeting.sort(key = lambda x :(x[1], x[0]))
count=0
end_time=0

for i in meeting:
    if i[0]>=end_time:
        end_time=i[1]
        count+=1

print(count)

💡시간복잡도

회의의 시작시간과 변경시간은 변하지 않으므로, 시간을 줄이기 위해 입력을 받을 때 리스트 대신 튜플을 이용했다.

위 리스트 사용, 아래 튜플 사용

큰 차이는 없지만 확실히 줄긴 하더라~~

 

또한 for문 내에서 인덱스를 이용해 배열에 직접 접근하는 것과 for i in list와 같이 요소를 복사하여 접근하는 것 중 어느 것이 더 시간이 빠를까 궁금해서 실험해보았다.

배열에 인덱스를 이용해 직접 접근

요소 접근

 

큰 차이는 없었지만, 의외로 요소로 접근하는게 조금 더 빨랐다. 요소를 복사하면 복사하는 시간과 메모리가 더 사용될 줄 알았는데, 메모리는 차이가 없었고 시간은 오히려 더 적게 들었다.

배열에 인덱스로 직접 접근하는데 시간이 걸리는 것 같다. ㅎㅎ 

 

왜 그럴까?

내 생각으로는 이 코드가 이중배열이므로 ..

 

for i in meeting: 에서 한번 복사를 하면, 
    if i[0]>=end_time: i에서 i[0]으로 한번에 바로 접근할 수 있다.
        end_time=i[1] 
        count+=1

 

그러나 배열에 인덱스로 접근하는 방법은 

for i in range(N):
    if meeting[i][0]>=end_time: meeting[i]에 접근한 후, meeting[i][0]으로 이중배열에 한단계 더 접근해야한다.
        end_time= meeting[i][1] 여기서도 접근을 총 두번 해야한다.
        count+=1

 

이런 접근 횟수에 따른 차이가 있지않을까?

혹은 인덱스 접근 시 meeting 배열에 저장된 메모리의 위치가 멀면 복사를 하는게 시간이 덜 걸릴 것 같다.

관련해서 파이썬 문서랑 c++의 범위 기반의 for문 문서를 찾아봤는데 파이썬 문서는 시간에 대한 언급은 없고 c++ 문서는 성능은 크게 차이나지 않는다고 적혀있었다. 성능에 큰 영향을 미치는 부분은 아니라 별 다른 언급이 없는 것 같다.

 

개인적으로 가독성 부분에서는 for문을 쓸 때 요소를 복사하는 방법이 더 좋은 것 같다.

 

(관련하여 더 자세히 알고 계시다면 댓글 부탁드립니다)

 

💡 느낀점 or 기억할 정보

알고리즘 공부를 처음 시작할 때 그리디 알고리즘을 배우며 풀었던 문제인데, 몇개월이 지나 다시 한번 풀어보았다. 옛날엔 너무 어려워서 풀기 어려웠는데 지금은 10분만에 풀어서 뿌듯하다. 늘긴 하는구나~~ 화이팅