프로그래머스 (Level 2) : 구명보트/ C++, Python, Greedy

문제

프로그래머스

 

 

한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한이 있는 구명보트가 있다.

 

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 무게 제한이 100kg이라면 

2번째 사람과 4번째 사람은 같이 탈 수 있지만 

1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 무게 제한을 초과해 같이 탈 수 없다.

 

input : 사람들의 몸무게를 담은 배열 people, 구명보트의 무게 제한 limit

output : 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값

 

 

 

 

풀이

 

people 배열을 오름차순 정렬 후 첫 번째와 마지막 무게의 합이 제한보다 적거나 같으면 둘다 pop

아니면 마지막 무게를 pop하는 방식으로 구현했다.

 

파이썬으로는 deque를 활용했고 (pop, pop_left)

C++은 vector가 입력자료형이어서 첫 번째 원소를 pop할때 erase(v.begin(), v.begin()+1) 를 썼더니

매번 벡터의 인덱스를 호출해서인지 효율성 두개가 틀리게 제출돼서

인덱스를 증가시켜 첫 번째 원소를 pop 하듯이 구현했다.

 

 

1. Python

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort() #오름차순 
    people=deque(people) #deque로 형변환
    while people:
        if len(people)>1 and people[0]+people[-1]<=limit:
            answer+=1
            people.pop()
            people.popleft()
        
        else:
            people.pop()
            answer+=1

    return answer

 

2. C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end());
    
    // 정확성 100%, 효율성 2/5개 time out
    // while(!people.empty()){
    //     int s=people.size();
    //     if(people.size()>1&&people[0]+people.back()<=limit){
    //         answer+=1;
    //         people.pop_back();
    //         people.erase(people.begin(),people.begin()+1);
    //     }
    //     else{
    //         answer+=1;
    //         people.pop_back();
    //     }
    // }
    
    int idx=0;
    while(idx<people.size()){
        if(people.size()>1&&people[idx]+people.back()<=limit){
            answer+=1;
            people.pop_back();
            idx+=1;
        }
        else{
            answer+=1;
            people.pop_back();
        }
    }
    return answer;
}