[프로그래머스][Level2] 구명보트 (파이썬)

---

문제출처

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

프로그래머스

---

문제를 스스로 해결하였는가?  ->  O

 남아있는 사람들 중 가장 무거운 사람과 가장 가벼운 사람이 짝찌어 보트를 타야한다는 아이디어만 떠오르면 큐 자료구조를 이용해 쉽게 풀리는 문제다. 다만 똑같은 아이디어로 투포인터를 사용해 풀 수도 있어서 투포인터도 공부할 겸 따로 정리한다.

---

필요한 배경지식

• 투포인터
• 스택/큐

---

아이디어

• 무인도에 남은 사람들 중 가장 무거운 사람과 가벼운 사람을 짝짓는다.
• 짝지은 두 사람의 몸무게가 limit를 초과하면 무거운 사람만 보트에 태우고 가장 가벼운 사람은 무인도에 남는다.

---

전체코드

큐 자료구조를 사용한 풀이

from collections import deque
def solution(people, limit):
    people.sort()
    people = deque(people)
    cnt = 0
    while len(people)!=0:
        cnt += 1
        pig = people.pop()
        if len(people)!=0 and pig + people[0] <= limit:
            people.popleft()
    return cnt

 

투 포인터를 사용한 풀이

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

코드가 단순해서 따로 설명은 필요없을 듯 하다.