Python으로 푸는 SW Expert Academy 5202. 화물 도크

SW Expert 아카데미 5202. 화물도크

 문제에서는 일정 시간동안 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면,

최대 몇대의 화물차가 이용할 수 있는지 알아내야 한다.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건  

1. 작업은 24시간 진행된다.

2. 작업 시작 시간은 매시 정각을 기준으로 하며, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.

문제 풀기 전 결정 사항

- 최대한 많은 화물차가 싣고 내릴 수 있도록 하려면 최단 시간에 업무를 종료하는 화물차를 우선으로 내보내야 한다.

- 모든 테스트 케이스를 입력받아 처리하지 않고 yield 키워드로 generator를 사용하여 각각의 케이스별로 input 데이터를 처리하여 결과 값을 출력한다.

문제 풀이 방법

이 문제는 그리디 알고리즘으로 해결하는 문제이다.

그리디 알고리즘은 미리 정한 기준에 따라서 매번 가장 좋아보이는 답을 선택해 나가는 알고리즘이다.

다만 탐욕 알고리즘이 동적 계획법보다는 효율적이나 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 하지 못한다.

이 문제에서는 최단 시간에 업무를 종료하는 화물차를 기준으로 정렬한 후 처리한다.

최단 시간에 업무를 종료하는 화물차를 기준으로 하기 때문에 여기선 그리디 알고리즘을 적용할 수 있다.

수도 코드

def greedy:

 while timetable:

pick available, fastest truck up

search All timetable and pick next available, fastest truck up

return total truck count

 파이썬 코드

# 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하려면
# 최단 시간에 업무를 종료하는 화물차를 우선으로 화물을 내보낸다
 
def gens(t):
    for i in range(t):
        n = int(input())
        timetable = []
        for j in range(n):
            time = tuple(map(int, input().strip().split(' ')))
            timetable.append(time)
        sorted_timetable = sorted(timetable, key=lambda  tup:tup[1])
        yield sorted_timetable
 
def greedy(sorted_timetable):
    truck_count = 0
    truck = sorted_timetable.pop(0)
    truck_count += 1 # 해당 트럭 이용
    flag = True
    while len(sorted_timetable) != 0 and flag:
        end_time = truck[1]
        for index, time in enumerate(sorted_timetable):
            if time[0] >= end_time:
                truck = sorted_timetable.pop(index)
                truck_count += 1
                sorted_timetable = sorted_timetable[index:]
                break
            # 마지막 index까지 찾지 못했으면 중단
            if len(sorted_timetable) - 1 == index:
                flag = False
                break
    return truck_count
 
 
if __name__ == "__main__":
    num = 0
    t = int(input())
    for schedules in gens(t):
        num += 1
        print('#{0} {1}'.format(num, greedy(schedules)))
 

#5202. 화물 도크 #python 5202. 화물 도크 #파이썬 5202. 화물 도크 #파이썬 화물 도크 #화물도크 #파이썬 5202 #파이썬 5202 화물 도크 #삼성 5202 화물도크 #5202 화물도크 #python 5202 화물도크 #5202 화물도크 python #5202 화물 도크 #python 5202 화물 도크 #5202 화물 도크 python