프로그래머스 코딩테스트 고득점 Kit_탐욕법(Greedy)_구명보트

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

  • 투 포인터 사용하기 위해 정렬
  • 각 포인터 left, right가 태울 수 있는 사람 중 가장 몸무게가 작은 사람, 몸무게가 큰 사람을 가르킴 (이미 태운 사람은 가르키지 X)
  • 다음과 같은 로직으로 보트에 태움
    포인터가 가르키는 사람의 합이 limit보다 작거나 같으면?
    -> 둘 다 태운다.
    크면?
    -> 몸무게가 제일 큰 사람을 태운다.

구현 코드 👇

def solution(people, limit):
    people.sort()
    
    answer = 0
    left, right = 0, len(people) - 1
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        answer += 1
            
    return answer

좋은 웹페이지 즐겨찾기