[프로그래머스] Level 2_구명보트(Greedy)

📌문제 유형

Greedy

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(실패)

 - 효율성 오래걸림

def solution(people, limit):
    answer = 0
    rescue = []
    real_limit = limit
    people.sort(reverse = True)
    
    #[80,70,50,50]
    for i in range(len(people)):
        rescue.append(people[i])
        limit = real_limit
        limit -= people[i]
        answer += 1
        
        for j in range(i+1,len(people)):
            if people[j] <= limit:  # 숫자가 같을때 
                rescue.append(people[j])
                limit -= people[j]
        
        if rescue == people:
            break
        
    return answer

2차 시도(정확성 : 60, 효율성: 0)

def solution(people, limit):
    answer = 0
    list_ = []
    people.sort(reverse = True)
    
    while len(people) > 0:
        list_.clear()
        sum_ = 0
        sum_ = people[0]
        list_.append(0)
        
        for i in range(1,len(people)):
            if sum_ + people[i] <= limit:
                sum_ += people[i]
                list_.append(i)
            else:
                continue
                
        answer += 1

        for i in list_:
            if i != 0:
                i -= 1
            del people[i]
               
    return answer

3차 시도(정확성 : 통과, 효율성 : 0)

 - del과 for문을 사용해서 효율성 0

def solution(people, limit):
    answer = 0
    real_limit = limit
    list_ = []
    
    while len(people) > 0:
        people.sort(reverse = True)
        limit = real_limit
        list_.clear()
        
        limit -= people[0]
        people.pop(0)
        people.sort()
        answer += 1
        
        for i in range(len(people)):
            if people[i] <= limit:
                limit -= people[i]
                list_.append(i)
            else:
                break

        for j in range(len(list_)):
            if j != 0:
                j -= 1
            del people[list_[j]]
               
    return answer

4차 시도(통과, 다른사람 풀이 이용)

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

def solution(people, limit):
    answer = 0
    people.sort()
    i, j = 0, len(people)-1
    
    while i <= j:
        answer += 1
        if people[j] + people[i] <= limit : 
            i += 1
        j -= 1
        
    return answer

 

📌다른 사람들의 풀이

1) deque 이용

 - deque의 특징

• deque에는 sort가 없음!
• deque.reverse()로 뒤집는 것만 가능
• deque.pop, deque.popleft만 가능(특정 인덱스만 꺼내지 못함)

 - 정렬 후 큰 값, 작은 값만 더하고 limit와 판단

• 더한 값이 limit보다 크면, 작은 값인 left 다시 넣기

from collections import deque

def solution(people, limit):
    result = 0
    deque_people = deque(sorted(people))

    while deque_people:
        left = deque_people.popleft()
        if not deque_people:
            return result + 1
        right = deque_people.pop()
        if left + right > limit:
            deque_people.appendleft(left)
        result += 1
    return result

 

📌리뷰

 - 삭제하지 않고 하나의 리스트로 문제에 접근할 수 있다

 - 그리디 : 정렬, 리스트 앞과 뒤의 값 빼내서 비교하는 방법 생각하기