화물 도크 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5022

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 5 20 23 17 20 23 24 4 14 8 18 10 14 23 2 19 1 22 12 24 21 23 6 15 20 24 1 4 6 15 15 16 15 18 19 2 7 11 15 13 16 23 24 2 14 13 22 20 23 13 19 7 15 5 21 20 24 16 22 17 21 9 24	#1 4 #2 4 #3 5

---

2. 문제풀이

그리디는 생각할때가 어렵지 막상 짜고나면 별거아닌 경우가 많다. 이번 경우는 작업시간을 떠나서 그냥 도크를 많이 사용하면 되는 문제이다. 간단한 그리디의 경우 정렬하면 풀리는 경우가 많은데 이번의 경우에는 끝나는 시간으로 정렬을 했다. 현재 작업하는 작업의 끝나는 시간과 리스트에 담긴 다음 작업시작시간을 비교하여 도크 이용이 가능하다면 answer를 늘려주고 시간을 갱신하는 방식을 이용했다.

---

3. 소스코드

 

#D3 5202 화물 도크
 
for t in range(int(input())):
    answer = 1
    N = int(input())
    time_list = [list(map(int, input().split())) for _ in range(N)]
    #끝나는 시간으로 정렬
    time_list.sort(key=lambda x: x[1], reverse=True)
    #제일빨리 끝나는 화물 가져오기
    end_time = time_list.pop()[1]
    #화물이 빌때까지 반복
    while time_list:
        s, e = time_list.pop()
        #이전화물끝나는 시간보다 늦게시작하면
        if end_time <= s:
            #끝나는 시간 갱신하고 answer 증가
            end_time = e
            answer += 1
    
    print('#{} {}'.format(t+1, answer))