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

문제

lv2. 구명보트

 

접근 방식

• 그리디와 투포인터를 이용해 해결할 수 있는 문제입니다. 이 문제는 마땅한 해결책을 찾지 못해 레퍼런스를 보며 이해한 문제입니다.
• 투포인터를 활용하기 위해 먼저 몸무게가 저장된 리스트를 오름차순 정렬해줍니다. 이 후, 시작 인덱스와 끝 인덱스를 각각 0과 len(무게 리스트)-1로 지정해 줍니다.
• 이 후, 시작 인덱스가 끝 인덱스보다 작거나 같을 동안, (가벼운 사람의 무게 + 무거운 사람의 무게) limit값 보다 작거나 같으면 시작 인덱스를 +1 해주고, 그렇지 않은 경우에는 끝 인덱스에 -1을 설정해줍니다.
• 시작 인덱스를 +1, 끝 인덱스를 -1로 설정한 부분은 각각 더 큰 값과 작은 값을 찾아 나가기 위해 지정한 걸로 이해하면 될 것 같습니다.
• 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 리턴해줍니다.

코드

def solution(people, limit):
    answer = 0
    #무게 순으로 정렬
    people.sort()
    #투포인터 선언
    s=0
    e=len(people)-1
    #시작 포인터가 끝 포인터보다 작을 동안
    while s<=e:
        #경우의수 + 1, (가벼운 사람의 무게 + 무거운 사람의 무게)가 limit을 넘으면, 한명만 태우는 경우이므로
        answer+=1
        if people[s] + people[e] <= limit:
            s+=1
        e-=1
    return answer