[코딩테스트] 프로그래머스 구명보트 파이썬(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/42885#

프로그래머스

from collections import deque
def solution(people, limit):
    boat = 0
    people = deque(sorted(people))
    while people:
        if len(people) == 1:
            boat += 1
            break
        if people[0] + people[-1] <= limit:
            people.popleft()
            people.pop()
            boat += 1
        else:
            people.pop()
            boat += 1
                

    return boat

 

처음에는 위의 코드가 아닌 값을 내림차순으로 정렬하고 앞에서 부터 순차적으로 값을 확인하면서 코드를 진행했는데

이 방법을 사용할 경우에는

[30, 40, 60, 60, 90], limit = 100 과 같은 케이스를 제대로 맞출 수 없었습니다.

내림차순으로 정렬 후 순차적으로 코드를 진행하면

(30, 40), (60),(60), (90) 처럼 4개의 보트가 필요하다고 나오는데

사실 (30, 60), (40, 60), (90)처럼 정답은 3개의 보트가 필요합니다.

 

내림차순으로 정렬후에 순차적으로 진행하지 않고 위의 코드처럼 오름차순으로 정렬후에

가장 작은 값과 가장 큰값을 비교하여 조건에 부합하면 두 값을 빼서 보트의 수를 늘려주는 방식을 사용하였습니다.

하지만 가장 작은 값과 가장 큰 값을 비교했을 때 limit보다 크다면 가장 큰 값만 빼고 가장 작은 값은 다른 값과 비교해 볼 수도 있도록 가장 큰 값만 제거하여 진행하였습니다.

마지막으로는 남아있는 사람들 중 비교할 수 있는 값이 없고 1명이라면 보트의 수를 늘려주고 반복문을 종료하였습니다.