[웅's 프로그래머스] 구명보트 - 파이썬(Python) 풀이

다른 것 보다도 문제를 풀면서 있었던 사고의 흐름을 적어보고자 한다.

 

먼저, 보트에는 무게 제한이 있기 때문에 최대한 무게 제한에 가까운 숫자로 보트를 꽉꽉 채워 넣는 것이 중요하다고 생각했다.

 

그렇게 하기 위해서는 무게가 많이 나가는 사람부터 태우고, 남는 무게 중 가능한 사람이 있으면 추가로 태우는 방식을 고려했다. 때문에 사람들을 무게 순으로 정렬했다.

 

그 다음은 반복문을 어떻게 돌까? 하는 고민이 들었다.

 

가장 큰 수부터 뽑고 남은 무게를 채울 수 있는 사람이 있는지 확인해야 하는데, 가장 작은 몸무게 부터 확인해야 할지, 그 다음으로 큰 몸무게 부터 확인해야할 지가 고민이었다.

 

결론은 그 다음 큰 수를 뽑을 경우 이전의 큰 수 보다 무조건 작기 때문에, 작은 수를 뽑을 때도 가장 작은 몸무게 부터 뽑자는 생각이 들었다. 때문에 가장 작은 몸무게의 시작점을 i, 가장 큰 몸무게의 시작점을 j 라고 두고 두 기준점을 하나씩 옮겨가면서 반복문을 돌았다. 

 

이러한 방법은 예전에 보았던 Quick Sort 방법에서 착안했다.

 

def solution(people, limit):
    people.sort()
    i, j, boat = 0, len(people)-1, 0
    while j>=i:
        boat+=1
        if people[i]+people[j] <= limit:
            i+=1
            j-=1
        else:
            j-=1

    return boat