[프로그래머스] 구명보트 풀이

 


1. 문제

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

2. 풀이

  • 사람들의 몸무게 순서대로 정렬합니다.
  • left, right 인덱스를 생성하여 양 옆으로 지정합니다. right는 현재 존재하는 요소들 중 최대, left는 최소입니다. left가 right 보다 커질때까지 계속해서 진행합니다.
    • left와 right가 같은 경우 사람이 1명 남아 있기 때문에, while 문을 종료합니다. (answer 1 증가, break)
    • left + right 인덱스의 사람의 몸무게가 limit 보다 적은 경우 하나의 보트에 태워서 보냅니다. 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 배에 태워서 보냅니다. (answer 1 증가, left 1 증가, right 1 감소)
    • 몸무게가 limit 보다 크면 right 인덱스에 해당하는 사람을 배에 태워서 보내고(answer 1 증가, right 1 감소) 계속해서 진행합니다.
def solution(people, limit):
    answer = 0    
    people.sort()
    left = 0
    right = len(people) - 1
    
    while left <= right:
        if left == right:
            answer += 1
            break
        if people[left] + people[right] <= limit:
            answer += 1
            left += 1
            right -= 1
        else:
            answer += 1
            right -= 1
        
    return answer