프로그래머스 - 구명보트 [파이썬]

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

프로그래머스

---

풀이 과정

limit의 무게 제한이 있는 2인용 구명보트에 임의의 무게를 가진 사람들을 모두 태우고 나가려면 구명보트가 몇 대가 있어야 하는지 구하는 문제이다.

 

투 포인터를 이용하여 문제를 쉽게 해결할 수 있다. 무게 배열을 오름차순으로 정렬하고, left 포인터를 0, right 포인터를 오른쪽 끝에 위치시키자.

 

people[left] + people[right]가 limit를 넘으면 people[right]는 배열 내의 어떤 사람이랑 짝을 지어도 무조건 limit를 넘게 된다. (정렬했으므로 people[left]가 무조건 최소 무게 사람) 따라서 right번째 있는 사람은 무조건 배를 혼자 타야 하므로 right 포인터를 1 감소시키고, 사용한 배의 횟수를 1 증가시켜주면 된다.

 

people[left] + people[right]가 limit를 넘지 않는다면, 2명이서 배를 탈 수 있으므로, left 포인터 증가, right 포인터 감소, 사용한 배의 횟수를 1 증가시켜주면 된다. 

 

 

첫번째 입출력 예시에 위의 알고리즘을 적용한다면

 

people.sort() -> [50, 50, 70, 80]

1. 50 + 80 안되므로 80kg 혼자 배에 태우고 right -= 1

2. 50 + 70 안되므로 70kg 혼자 배에 태우고 right -= 1

3. 50 + 50 가능하므로 둘이 배에 태우고 left += 1, right -= 1

4. left, right가 교차했으므로 -> 모든 사람이 배에 탔으므로 사용한 배의 횟수 출력

 

순으로 돌아갈 것이다.

---

소스 코드

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