[Python/Programmers] 구명보트

문제

1. 난이도: 프로그래머스 Level 2

2. 문제요약:

구명보트는 최대 2명이 탈 수 있다.
또한 구명보트의 무게 제한은 문제의 입력값(limit)으로 주어진다.
사람들의 몸무게가 담겨 있는 리스트는 문제의 입력값(people)으로 주어진다.
최소 개수의 구명보트를 사용해 모든 사람들을 구출하려고 할 때의 구명보트 개수를 구하여라.

3. 문제핵심: 그리디(Greedy) 알고리즘

• 그리디 알고리즘: 선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 그리디 알고리즘의 최종적인 해답이 항상 최적의 해답은 아니다.
• ex) 동전의 개수를 최소로 하는 동전의 조합

내 코드

첫 번째 시도(정확도 O 효율성 X)

def solution(people, limit):
    move = 0
    people.sort()
    while len(people) >=2:
        maxKg = people.pop()
        move += 1
        possible = [kg for kg in people if kg+maxKg<=limit]
        if possible:
            possible.pop()
            people = possible + people[len(possible)+1:]
            
    if people:
        return move+1
    else:
        return move

• while 문 안의 possible = [kg for kg in people if kg+maxKg<=limit] 때문에 => O(N^2)
  

두 번째 시도(통과)

from collections import deque

def solution(people, limit):
    move = 0
    people.sort()
    people = deque(people)
    
    maxKg = people.pop()
    while len(people) > 1:
        if people[0] + maxKg <= limit:
            people.popleft()
        move += 1
        maxKg = people.pop()
        
    if people:
        if maxKg + people[0] <= limit:
            return move+1
        else:
            return move+2
        
    return move+1

• 아이디어
  - maxKg + minKg > limit이면 더 이상 체크할 필요 없다
  - maxKg + minKg 은 다음에 올 maxKg + minKg 보다 항상 크거나 같다
  -> 따라서, 위의 list comprehension 코드를 작성할 필요가 없다.
• while문 밖으로 나오는 경우
  1. len(people) == 1
  • maxKg = 70, people[0] = 20, limit = 100
  • maxKg = 70 people[0] = 50 , limit = 100
    2. len(people) == 0
  • 1명만 남은 경우
    

이상코드

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

• 아이디어
  - 전체 사람 수 - 짝지어진 수 = 사용된 구명보트의 개수
  - minKg의 인덱스와 maxKg의 인덱스만 바꿔주면 되지, 굳이 pop, popleft할 필요 없으므로 list로도 간단히 구현 가능