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

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

# 문제분류가 Greedy로 되있긴 한데.. greedy가 솔직히 제일 어려운 것 같다.

  쉬운 문제랑 개념자체는 쉬운데 그냥 분류없이 문제를 봤을 때

  '아, 이건 그리디로 풀어야겠다.'라고 떠올리기도 힘들고 그걸 증명해야하기 때문에 더 어려운 것 같다.

 

# 풀고보니 이분탐색 느낌도 나고 '투 포인터'인 것 같기도 하다.

def solution(people, limit):
    answer = 0
    people.sort()
    left, right = 0, len(people) - 1
    # left가 right보다 작은 동안 반복문 돌기
    while left < right:
        # 두 포인터가 가리키는 값의 합이 limit보다 작으면 그 두 사람을 태우고 left 1증가, right 1감소
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            # limit보다 크면 무거운사람 한명 태우고 right만 1감소
            right -= 1
        answer += 1
    # left와 right가 같으면 한명 남은 것이므로 answer에 1증가, 아니면 모두 보트에 탄 것이므로 answer에 증가 x
    if left == right:
        answer += 1
        
    return answer

 

(프로그래머스 level: 2)