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

문제

문제 설명

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

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

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

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

입력 & 출력

입출력 예

peoplelimitreturn

[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

풀이 과정

1. 오른쪽 왼쪽 인덱스의 개념으로 접근합니다. 양쪽 인덱스를 변수 선언합니다.

2. while문을 순회하면서 연속적인 조건문 판별을 진행할 것인데 여기서 탈출 조건은 idx 양쪽 값이 같거나 반전될 경우입니다. 이 두 가지 경우일 때는 break 문을 호출하여서 탈출할 수 있게 구성합니다.

3. boat 변수는 boat 한대를 만들었다고 생각이 될 경우에 증가할 수 있게 구성하였는데 이런 경우는 오른쪽 인덱스가 왼쪽 인덱스의 값과 같을 경우, 최대 값과 최솟값의 값의 합이 limit 값보다 크지 않을 경우, 이와 반대되는 경우를 생각할 수 있으며 각각 오른쪽 인덱스와 왼쪽 인덱스가 같으면 해당 값을 마지막 보트로 만들고 while문 탈출 2번째 경우는 양쪽 인덱스 값을 작은 인덱스는 더해주고 큰 인덱스는 빼면서 범위를 좁혀주고 두 값의 합이 limit보다 클 때는 가장 큰 숫자만 하나 boat에 태운다고 생각하고 가장 큰 숫자와 관련 있는 인덱스 변수만 1 올려주면서 반복을 하게 되면 원하는 값을 얻을 수 있습니다.

 

코드

def solution(people, limit):
    people.sort(reverse=True)
    people_max_idx = len(people) - 1
    people_min_idx = 0
    boat = 0

    while 1:
        people_max = people[people_min_idx]
        people_min = people[people_max_idx]
        if people_max_idx == people_min_idx:
            boat += 1
            break
        elif people_max + people_min <= limit:
            people_max_idx -= 1
            people_min_idx += 1
            boat += 1
            if people_max_idx < people_min_idx:
                break
        else:
            people_min_idx += 1
            boat += 1