[탐욕법(Greedy)] 구명보트 - Python / JavaScript

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

프로그래머스

 

[문제 간단 요약]

1. 구명보트에 최대 2명 씩 탈 수 있는 데, 무게 제한이 있을 때 최대한 적게 구명 보트를 사용하여 모든 사람을 태우는 구명보트의 갯수를 구하는 문제  

[문제 해결 방안]

1. 가장 무게가 많이 나가는 사람과 가장 적게 나가는 사람을 우선 선정

2. 최대 구명 보트 무게가 초과될 때 가장 적제 무게가 나가는 사람을 내리게 하기

3. 다음 구명 보트에 위의 방법 반복하여 구명보트 최소 갯수 구하

 

[문제 해결 코드 - python]

- 큐를 활용하여 문제 해결

from collections import deque
def solution(people, limit):
    answer = 0
    sort_people = sorted(people, key=lambda x:-x)
    q = deque(sort_people)
    while q:
        if len(q) == 1:
            answer+=1
            break
        max_weight = q.popleft()
        min_weight = q.pop()
        weight = max_weight + min_weight
        if weight > limit:
            q.append(min_weight)
        answer+=1
    return answer

 

[문제 해결 코드 - javascript]

- 투포인트 알고리즘을 활용하여 문제 해결

function solution(people, limit) {
    var answer = 0;
    let min_idx = 0;
    let max_idx = people.length - 1;
    people = people.sort((a,b) => a-b);
    while (min_idx <= max_idx) {
        let weight = people[min_idx] + people[max_idx];
        if (weight <= limit) {
            min_idx += 1;
        } 
        max_idx -= 1;
        answer += 1;
    }
    
    return answer;
}