[🥲 프로그래머스] 구명보트 - 탐욕법

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

코딩테스트 연습 - 구명보트

 

예전에 푼 문제인데 또 똑같이 시간초과함ㅋㅋㅋㅋㅋㅋ 인간은 망각의 동물...... 

 

✅ 내가 푼 풀이

# 1차시도 - 시간초과
def solution(people, limit):
    people.sort()
    count = 0
    while people:
        person = people.pop(0)
        
        if not people:
            count += 1
            break
            
        for i in range(len(people)-1,-1,-1):
            if person+people[i] <= limit:
                people.pop(i)
                break
        count += 1
        
    return count

 

# 2차시도 - 통과
def solution(people, limit) :
    answer = 0
    people.sort()
    
    left = 0 # people의 첫번째
    right = len(people)-1 # people의 마지막
    
    while left <= right:
    	# people의 가장 작은값과 큰 값이 합친 것이 limit보다 크다면 (1명만 탈 수 있다)
        if people[left] + people[right] > limit: 
            right -= 1 # 큰 값을 한칸 앞으로 당겨줌
        else:
        # 같으면 작은 값은 한칸 위로, 큰 값은 한칸 앞으로 (2명이 탈 수 있다)
            left += 1
            right -= 1
        answer += 1
        
    return answer

꺼진 불도 다시 보자는 속담이 떠올랐다....

 

+ 이 문제 다시 풀었는데 같은 알고리즘이라도 리스트가 아니라 queue로 변경하면 속도가 빨라짐!

from collections import deque
def solution(people, limit):
    count = 0
    people.sort(reverse=True)
    people = deque((people))

    while people:
        p = people.popleft()
        
        if not people:
            count += 1
            break
            
        if people[-1] + p <= limit:
            people.pop()
        
        count += 1
    return count