[Programmers] L2. 구명보트 (Python/투 포인터)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

1️⃣ 정렬  (O(nlog⁡n)시간)

• 사람들의 몸무게 리스트를 오름차순으로 정렬한다.
• 이렇게 하면 가장 가벼운 사람과 가장 무거운 사람을 효율적으로 짝지을 수 있다.

2️⃣ 투 포인터 사용 (O(n) 시간)

• 리스트의 가장 가벼운 사람(왼쪽 포인터)과 가장 무거운 사람(오른쪽 포인터)을 확인한다.
• 두 사람의 몸무게 합이 보트의 무게 제한을 초과하지 않으면, 두 사람을 한 보트에 태운다(양쪽 포인터를 이동).

3️⃣ 혼자 태우기

• 두 사람의 몸무게 합이 무게 제한을 초과하면, 가장 무거운 사람만 보트에 태우고 오른쪽 포인터를 이동한다.

4️⃣ 반복

• 왼쪽 포인터가 오른쪽 포인터를 넘을 때까지 위의 과정을 반복한다.

5️⃣ 결과 반환

• 필요한 보트의 개수를 계산하여 반환한다.

 

[Two-Pointers(투 포인터) 개념 정리] 🔗 https://dev-cloud.tistory.com/420

Solution

def solution(people, limit):
    answer = 0
    people = sorted(people)
    start = 0
    end = len(people) - 1
    while start <= end:
        if people[start] + people[end] <= limit:
            start += 1
            end -= 1
            answer += 1
        else:
            answer += 1
            end -= 1
    return answer

---

👩‍💻 회고

처음엔 조합을 사용하여 구현하고 제출했는데, 실행 시간도 오래 걸리고 오답이 많았다. 투 포인터 알고리즘을 이용하니 훨씬 효율적이고 더 쉽게 풀 수 있었다.

---