[Greedy / 프로그래머스] 42885번 : 구명보트

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

 

Level2 문제다!

 

문제 이해

하나의 보트에 최대 2명, 두 사람의 무게 합이 보트 제한 무게보다 적어야 한다 

만약 이웃한 두 사람의 무게의 합이 무게 제한보다 크다면 각각 하나씩 타야한다 

 

풀이 이해

사용하는 보트 수가 최소가 되기 위해서는 남은 사람 중 몸무게가 가장 작은 사람과 가장 큰 사람을 같이 태워야한다(최적해)

이걸 알기위해 people 리스트를 오름차순 정렬해주고, 빠르게 연산하기 위해 deque()선언을 해준다 

 

남은 사람이 한 사람이라면 보트 수만 추가하고 끝낸다 

남은 사람이 2명 이상이고, 남은 사람 중 가장 가벼운 사람과 무거운 사람이 보트를 탈 수 있을 때 보트를 추가해주고, 

양 끝 원소를 삭제해준다 

 

아닌 경우라면 그냥 각자 하나씩 보트를 탄다 

 

- 정답 풀이 :

from collections import deque

def solution(people, limit):
    people.sort()
    answer = 0 
    people = deque(people)
    
    while people:
        if len(people) == 1:
            answer += 1
            break
        #가장 무거운 사람과 가장 가벼운 사람이 탈 수 있을 때
        elif people[0] + people[-1] <= limit:
            answer += 1
            people.pop()
            people.popleft()
        #가장 무거운 사람이 하나의 보트만 탄다
        else:
            answer += 1
            people.pop()
            
    return answer

 

- 시도해본 풀이 :

지금보니 완전 삽질한 풀이다,,,

정렬한 후 0 인덱스부터 시작해서 보트에 2명이 있다면 다음 보트를 넘기고

1명이 있고, 보트에 탄 사람의 무게와 아직 보트에 없는 사람의 무게 합이 제한 무게 이하면 추가하고

아니면 각자 타는 걸로 생각했는데 

 

뭔가 풀이가 명확하지가 않다 

명확하게 해보자

def solution(people, limit):
    people.sort()
    count = 1 #보트 수 
    boat = 1 #보트에 있는 사람 수 
    weight = people.pop(0) #보트에 있는 사람의 총 무게 
    
    for person in people:
        if boat == 2:
            count += 1 
            boat = 1
            weight = person
        elif boat < 2:
            if weight + person <= limit:
                weight += person 
                boat += 1
            else: 
                boat = 1 
                count += 1
                weight = person 
                                
    return count