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

문제 링크

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

문제 설명

구명보트에 최대 두 명이 탈 수 있다.
구명보트의 무게 제한과 사람들의 몸무게 리스트가 주어졌을 때, 구조를 위해 필요한 최소 구명보트 갯수를 반환하라

1차 시도 - 불통

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

첫 시도는 이게 아니었지만... 뭐 문제를 잘 읽어야겠다고 다시 다짐한다. (구명보트에 탈 수 있는 최대 인원은 2명이다.)
난 무거운 사람을 많이 태워가면 좋은거지~ 라고 생각하고, 일단 먼저 가장 무거운 사람 태우고, 그 다음 무거운 사람이 탈 수 있으면 타고, 아니면 가장 가벼운 사람이 탈 수 있는 경우 태우려고 했는데! 효율성 측면에서 문제가 생긴다.
찾아보니 pop(0)을 하면 O(1)이 아닌 O(N)이어서 이 문제에선 list의 pop을 쓰면 통과가 어려운듯하다.
*아 그리고 while, if문 등에서 리스트 그 자체는 비어있으면 False, 아니면 True를 반환한다.

2차 시도 - 통과

질문하기 를 보니, 효율성을 통과하기 위해선 투포인터 알고리즘을 써야한다길래 그게 뭐지 했는데 pop, remove와 같은 함수를 사용해 실제 리스트를 수정하지 않고 두 개의 점의 위치를 기록하며 처리하는 알고리즘 이라고 한다. 즉 이 문제에선 리스트를 정렬 후 min, max에 포인터를 두고 인덱스로 조건 충족 여부를 확인하는거다.

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

이 코드도 사실 마음에 들진 않는데.. 암튼 리스트를 직접 수정하지 않고 포인터를 활용하는 방법이다.
아니 근데 난 잘 모르겠다. 몸무게가 가장 많이 나가는 두 명이 같이 나가는 경우가 있다해도 이 코드가 맞나? 오 그렇긴 하지... 차피 2명 나가는 게 최대니까?
에휴 암튼 힌트를 많이 보고 푼 문제여서 아쉬움이 남지만 투 포인터라는 방법을 익혔다고 생각하자!

+) 3차 시도

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

return을 전체 사람 수 - 두명이서 나간 보트 수하면 좀 더 간단하게 쓸 수 있다.
한 보트에 최대 두명이 탑승 가능하다는 게 아주 큰 정보였다.

정리

• 투포인터: 리스트에 두 지점의 위치를 기록하며 처리하는 알고리즘
• 빈 리스트 확인: 길이를 통해 확인할 수도 있고, while, if문 등에서는 리스트 자체가, 비어있다면 False, 아니면 True를 반환한다.
• pop(0)은 O(N): 그렇단다. 데이터를 지우고 한 칸 씩 앞으로 당겨야 해 O(1)이 아닌 O(N). 이 문제에선 deque를 사용해 leftpop을 사용하는 것도 하나의 방법이라고 한다.

# deque를 이용한 방법
from collections import deque

def solution(people, limit):
    people = deque(sorted(people))
    cnt = 0
    
    while people:
        tmp = 0
        tmp+=people.pop()
        if people:
            if tmp+people[-1]<=limit:
                tmp+=people.pop()
            elif tmp+people[0]<=limit:
                tmp+=people.popleft() #pop(0)만 popleft()로 변경해줬다.
        cnt+=1
    return cnt