99클럽 코테 스터디 17일차 TIL + 탐욕법(Greedy) : 구명보트

문제

링크텍스트

풀이

import heapq
def solution(people, limit):
    n = len( people )
    if n == 1:
        return 1
    elif n == 2:
        return 1 if sum(people) <= limit else 2
    heapq.heapify(people)
    p = []
    for i in range(n):
        heapq.heappush(p,-people[i])
    cnt = 0
    while len(p)+len(people) > n:
        cnt += 1        
        if people[0]-heapq.heappop(p) <= limit:
            heapq.heappop(people)
    return cnt

for i in range(4):
# for i in [2]:
    print(f'test case: {i}')
    if i == 0:
        people, limit, r = [70, 50, 80, 50], 	100, 	3
    elif i == 1:
        people, limit, r = [70, 80, 50], 	100, 	3
    elif i == 2:
        people, limit, r = [70], 	100, 	1
    elif i == 3:
        people, limit, r = [50,25,25,70], 	100, 	2
    a = solution(people, limit)
    print(a)
    print(r)    

• list로는 시간초과가 계속 발생하여, heap을 사용하였습니다.
• 처음에는 하나의 구명보트에 세 명 이상도 고려였으나, 다행히 문제에서 최대 두 명씩 밖에 탈 수 없다고 합니다.
• heappop()을 사용하여 시간을 줄이기 위해, 오름차순과 내림차순 각각의 heap을 구성하였습니다.
• 또한 초기에 1명인 경우와 2명인 경우에 바로 return하도록 하였습니다.
• 문제정의에는 greedy 탐색법이라 되어있는데 아직 잘 모르겠습니다. [조이스틱](https://school.programmers.co.kr/learn/courses/30/lessons/42860) 를 보고 공부해야겠습니다.

결과