[고득점 Kit(탐욕법)] 구명보트 (Python)

코딩테스트 연습 - 구명보트

 

풀이

 people을 정렬한 상태로 만들어준다. 그 후 left와 right를 두어 현재 가장 가벼운 사람과 무거운 사람을 최대한 같이 태울 수 있도록 해주었다. 먼저 보트에 가장 무거운 사람을 태웠을 때 limit보다 작다면 무거운 사람을 태우고 right 인덱스를 -1 해준다. 그 후 가장 가벼운 사람을 태웠을 때 limit보다 작다면 가벼운 사람을 태우고 left 인덱스를 +1 해준다. 

 

 이 때 flag를 사용했는데 만약 flag가 False라면 현재 left, right 인덱스에 해당하는 사람을 모두 태울 수 없는 상태, 즉 보트에 최대한 사람을 태운 상태를 뜻한다. 그럴 경우 보트를 비우고 다시 보트에 left와 right 인덱스에 해당하는 사람을 태우는 방식으로 진행된다. 

 

코드

def solution(people, limit):
    answer = 0

    people.sort() # 먼저 사람들을 무게 순으로 정렬

    left = 0 # 가벼운 사람부터 탐색하기 위한 인덱스 
    right = len(people) - 1 # 무거운 사람부터 탐색하기 위한 인덱스

    now = 0 # 현재 보트에 태운 사람들의 무게 
    while left <= right:
        # 보트에 사람을 추가로 태울 수 있는지 판단하기 위한 boolean 변수
        # left와 right를 탐색했는데 여전히 False라면 추가로 사람을 태울 수 없음을 뜻한다.
        flag = False  

        # 먼저 무거운 사람을 태울 수 있는지 체크 
        if now + people[right] <= limit:
            now += people[right]
            right -= 1
            flag = True 
        
        if right < left:
            break 
        
        # 다음으로 가벼운 사람을 태울 수 있는지 체크
        if now + people[left] <= limit:
            now += people[left]
            left += 1
            flag = True
        
        # 보트에 더 이상 사람을 태울 수 없으므로 보트를 비우고 새로운 보트에 사람들을 태운다.
        if not flag:
            now = 0 
            answer += 1

    # 현재 보트에 사람이 있는 상태면 추가로 answer + 1을 해준다.
    if now != 0:
        answer += 1

    return answer