[SWEA 5202번] 화물 도크 - 파이썬(python)

SW Expert Academy

분류

• 탐욕 알고리즘(greedy)

문제

24시간 운영되는 물류센터에는 화물을 싣고 내리는 도크가 설치되어 있다.

0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오.

신청서에는 작업 시작 시간과 완료 시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.

예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 신청서 N이 주어지고, 다음 줄부터 N개의 줄에 걸쳐 화물차의 작업 시작 시간 s와 종료 시간 e가 주어진다.

1<=N<=100, 0<=s<24, 0 ＜ e ＜= 24

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이

• 백준의 회의실 문제와 매우 유사한 문제이다.
• 종료시간이 빠른 순에서 종료시간과 시작시간을 맞추어서 횟수를 카운트한다.
• 먼저 시작 시간대로 정렬한 후 종료시간으로 다시 정렬한다.
• 종료시간이랑 다음 시작시간을 비교하여 풀이한다.

코드

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    time=[]
    cnt=1
    for _ in range(N):
        s, e = map(int, input().split())
        time.append([s,e])

    time.sort()
    sort_time=sorted(time, key=lambda x:x[1])

    end = sort_time[0][1]
    for i in range(1, N):
        if sort_time[i][0]>=end:
            cnt+=1
            end = sort_time[i][1]
    print(f'#{test_case} {cnt}')