[프로그래머스] 구명보트

매일매일 문제를 풀고 있다... 오늘은 아마 프로그래머스 푸는 사람이면 다 풀어봤을 '구명보트' 문제를 풀어보자...!

 

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

그리디 알고리즘을 풀어봤다. 그리디 알고리즘은 함정에 빠지기 쉬운 문제로 조건을 잘 살펴야 한다.

 

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

 

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

50 + 50 -> 1개

70 -> 1개

80 -> 1개

합 3개의 구명보트가 필요하다.

 

풀이 방법

이 문제는 효율성이 있어서 pop이나 append를 남발하면 안 된다. 그러므로 배열 삽입 삭제 없이 인덱스를 움직이는 것으로 문제를 해결했다. 변수 First와 변수 Last를 선언하여 케이스별로 컨트롤했다.

🔴 people [First]와 People [Last]를 더했을 때 Limit값 이하 -> First+1 , Last-1 하고 Return 값도 하나 늘림.

🟡 people [First]와 People [Last]를 더했을 때 Limit값 초과  -> Last -1 하고 Return 값도 하나 늘림.

마지막으로 Last가 First변수 같으면 Return 값을 하나 늘리고 동작을 멈췄고(🟢), 크면 그냥 동작을 멈췄다(🔵). 

예를 들면 People 리스트가 [10,20,30,40,60,60,70,80], Limit는 70일 경우.

First	Last	People[First]+People[Last]		Answer	Case
0	7	People[0]+People[7] = 90	Last-=1	1	🟡
0	6	People[0]+People[6] = 80	Last-=1	2	🟡
0	5	People[0]+People[5] = 70	First+=1, Last-=1	3	🔴
1	4	People[1]+People[4] = 70	Last-=1	4	🟡
1	3	People[1]+People[3] = 70	First+=1, Last-=1	5	🔴
2	2			6	🟢

 

왜?

해당 문제의 포인트는 보트에 두 명을 태울 수 있는지 한 명을 태울 수 있는지 판단하는 것이라고 생각한다.

이걸 판단할 수 있는 방법은 태우지 않은 사람 중 무게가 가장 많이 나가는 사람과 가장 적게 나가는 사람을 더하여 Limit이 넘는지 판단하고 Limit을 넘으면 무게가 많이 나가는 사람은 구명보트에 태워 보내는 게 가장 적절하다고 생각하여 해당 풀이를 적용하였다.

 

코드

def solution(people, limit):
    answer = 0
    people.sort()# 정렬
    if len(people)==1:# 1은 웬만하면 예외처리 하는게 좋음.
        return 1
    first=0# 처음과 끝 인덱스 설정
    last=len(people)-1#
    
    while True:
        if last==first:#🟢 
        # 해당 케이스는 🟡케이스로 끝이 난 경우인데, 
        # 이럴 경우는 앞에 있는 사람은 따른 보트에 태워보내야하기 때문에 보트를 추가한다. 
            answer+=1
            break
        if last<first:#🔵 
        #이 경우는 완벽히 다 보트를 탄 경우이기 때문에 보트를 추가하지 않아도 된다.
            break
            
        if people[first]+people[last]<=limit: #🔴 # 두명씩 태워보내는 케이스
            answer+=1
            first+=1
            last-=1
        else:#🟡 #한명씩 태워보내는 케이스
            last-=1
            answer+=1
    
    return answer

 

실행 결과