파이썬 SW문제해결 응용_구현 - 03 탐욕 알고리즘

5201. [파이썬 S/W 문제해결 구현] 3일차 - 컨테이너 운반

어려웠던 점

• 그리디 방식(큰 것부터 정렬) 하는 아이디어를 생각해내지 못했다.
• 리스트 두 개를 받아오는 함수라서, 이중 for문을 돌려야 하나? 란 생각이 들어 혼란스러웠다.

해결방안

• 구하고자 하는 것은 cargo_weight 데이터이므로 두 리스트를 비교할 때 이중 for문을 돌릴 필요가 없다.
• 한개의 리스트를 기준으로 조건문을 걸고, 조건을 충족하면 인덱스를 추가하는 방식으로 진행이 가능하다.
• 종료 시점은 인덱스가 특정 기준을 충족시켰을때 반복문을 중단하는 break를 사용한다.

예시코드

def max_cargo(cargo_weight, truck_ability):
    sorted_cargo_weight = sorted(cargo_weight, reverse=True)
    sorted_truck_ability = sorted(truck_ability, reverse=True)

    idx = 0
    total = 0
    # 무거운 것부터 차례대로 담을 수 있는지 확인한다.
    for weight in sorted_cargo_weight:
        # 트럭 용량이 화물보다 크거나 같으면 화물을 추가하고 다음 트럭으로 넘어간다.
        if weight <= sorted_truck_ability[idx]:
            total += weight
            idx += 1
            # 더 이상 담을 트럭이 없다면 탐색을 종료한다.
            if idx == len(sorted_truck_ability):
                break
    return total

T = int(input())

for tc in range(1, T + 1):
    N, M = map(int, (input().split()))
    cargo_weight = list(map(int, input().split()))  # [int(x) for x in input().split()]
    truck_ability = list(map(int, input().split())) # [int(x) for x in input().split()]

    print("#{} {}".format(tc, max_cargo(cargo_weight, truck_ability)))

 

5202. [파이썬 S/W 문제해결 구현] 3일차 - 화물 도크 

해결방안

• 인풋을 튜플을 담은 리스트 형태로 받아온다.
• 종료 시간을 기준으로 정렬한다. (람다함수 사용하여 sort함수를 key 기준으로 정렬)
• 리스트를 순회하며 가장 빠르게 시작하는 화물차를 차례로 담는다.
• 화물차의 수를 최종 프린트한다.

import sys
sys.stdin = open('input.txt')

def cargo_calender(board):
    # 종료 시간을 기준으로 정렬한다.
    sorted_list = sorted(board, key=lambda cargo: cargo[1])

    # 가장 빠른 종료시간을 담는다.
    cargo_schedule = [sorted_list[0]]

    # 가장 빠르게 시작하는 화물차를 차례로 담는다.
    for cargo in sorted_list:
        if cargo[0] >= cargo_schedule[-1][1]:
            cargo_schedule.append(cargo)

    return cargo_schedule


T = int(input())

for tc in range(1, T + 1):
    N = int(input())

    # 튜플이 담긴 리스트로 받아온다.
    board = [tuple(map(int, input().split())) for _ in range(N)]

    print("#{} {}".format(tc, len(cargo_calender(board))))