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

 

📌문제

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

 

🎖️난이도

Level 2

 

✔️풀이

# sol1) deque, popleft, pop
from collections import deque

def solution(people, limit):
    people.sort() # [10, 50, 50, 70, 80, 100] 
    queue = deque(people)
    cnt = 0
    
    while queue:
        j = len(queue) - 1
        if queue[0] + queue[j] <= limit:
            queue.popleft() # ***리스트 & pop(0) 보다 빠름***
        cnt += 1
        if queue : queue.pop()
        
    
    return cnt

# sol2) pop안쓰고 투포인터로 (더 빠르고 메모리 덜 차지)
def solution(people, limit):
    people.sort()
    cnt = 0
    i, j = 0, len(people)-1
    
    while i <= j:
        if people[i] + people[j] <= limit:
            i += 1
        cnt += 1
        j -= 1
        
    return cnt

 

# 오답 (정확성 정답, 효율성 오답 : tc 1번)
def solution(people, limit):
    people.sort() # [10, 50, 50, 70, 80, 100] 
    cnt = 0
    
    while people:
        j = len(people) - 1
        tmp = people[0]
        if tmp + people[j] <= limit:
            people.pop(0) # ***리스트 & pop(0)은 시간 초과의 원인***
        
        cnt += 1
        if people : people.pop() 
        
    
    return cnt

 

🧠노트

문제 조건에서 단 2명까지만 태울 수 있다고 했으므로,

정렬 후 가장 가벼운 사람부터(i++) 보트에 일단 태우고

그 다음에 남은 한 자리에 제일 무거운 순서대로(j--) 태워 보낼 수 있는지 체크해주면 된다!

 

만약 가장 가벼운 사람 태우고 남은 자리에 가장 무거운 사람을 태울 수 없다면

그 사람은 혼자 타야하는 사람이고,

그것보다 한층 덜 무거운 사람이 탈 수 있는지 순차적으로 체크해주면 된다. 

 

맨 처음에는 list와 pop(0) 등을 이용해서 풀었는데, 걱정한 것과 같이 효율성에서 오류가 났다.

이때, 바로 deque를 import해 queue와 popleft()를 사용해줬더니 정답!

 

cf. list와 pop()을 이용해서 시간초과가 난다면? 
👉 1. from collections import deque 후 queue = deque([]) 사용!! 
👉 2. pop을 안쓰고 포인터(인덱스)를 이용하는 방법 생각!!

 

🔍참고

-