프로그래머스 - 구명보트 / C++

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

코딩테스트 연습 - 구명보트

 

 

문제 풀이

아이디어는 쉽게 떠올랐다.

주어진 사람들의 무게를 정렬 후 최소 무게 + 최대 무게를 해서 limit이 넘어가면 최대 무게인 사람을 혼자 태우고 해당 인원을 pop한 뒤 다시 그 다음으로 무거운 사람을 최대 무게로 두는 방식으로 반복하려 했다. 그런데 실제로 원소들을 pop하다보니 시간 초과가 나서 인덱스를 다루는 방식으로 변경하였다.

 

소스 코드

효율성 테스트 실패

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    
    int maxVal = people.back();
    int minVal = people.front();
    
    while(!people.empty()){
        if(maxVal + minVal > limit){
            people.pop_back();
            answer++;
            maxVal = people.back();
        }
        else {
            if(people.size() == 1){
                answer++;
                break;
            }
            people.pop_back();
            people.erase(people.begin());
            answer++;
            maxVal = people.back();
            minVal = people.front();
        }
    }
    
    return answer;
}

 

통과한 코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    
    int maxIdx = people.size() - 1;
    int minIdx = 0;
    
    while(minIdx < maxIdx){
        if(people[maxIdx] + people[minIdx] > limit){
            answer++;
            maxIdx--;
        }
        else {
            maxIdx--;
            minIdx++;
            answer++;
        }
    }
    
    if(maxIdx == minIdx){
        answer++;
    }

    return answer;
}