[프로그래머스] 구명보트 C++

programmers.co.kr/learn/courses/30/lessons/42885#

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

구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

 문제 조건을 제대로 읽지 않아 삽질 한 문제. vector<bool>을 따로 만들어 사용 여부를 체크하다가 포기하고 3명이상 탈 경우를 고려해서 , 힙을 이용하여 풀었다.

 문제만 제대로 읽었으면 Leetcode에서 유명한 twoSum 문제와 풀이방법이 같았음을 알 수 있었는데 아쉽다. 풀이는 매우 간단하다.

int solution(vector<int> people, int limit) {
    int answer = 0;
    int left = 0;
    int right = people.size()-1;

    sort(people.begin(), people.end());

    while(left<=right){
        if(people[left]+people[right]<=limit){
            left++;
            right--;
        } else right--;
        answer++;
    }
    return answer;
}

 

 아래는 문제를 제대로 읽지 않고 푼 풀이. 몸무게가 40,40,40 구명보트 최대용량이 200일때 1번에 태울 수 있을 거라고 생각하여 힙을 사용하였다. 정확성 테스트는 통과하였으나 효율성 테스트를 통과하지 못했다. 사실 효율성 테스트가 있을 줄 몰랐다. 만약 구명보트 인원제한이 없었다면 좋은 풀이 방법이었을 듯. 문제를 보자마자 바로 풀 생각을 하지 말고 잘좀 읽어야겠다.

// #include <functional>  // make_heap
    bool smaller(int a, int b){ return a>b; }
    bool bigger(int a, int b){ return a<b; }

    int solution(vector<int> people, int limit) {
        int answer = 0;

        while(!people.empty()){
            make_heap(people.begin(),people.end(),bigger);
            pop_heap(people.begin(),people.end(),bigger);
            int rest = limit - people.back();   people.pop_back();

            make_heap(people.begin(),people.end(),smaller);
            pop_heap(people.begin(),people.end(),smaller);
            while(!people.empty() && people.back() <= rest){
                rest -= people.back();  people.pop_back();
                pop_heap(people.begin(),people.end(),smaller);
            }
            answer++;
        }
        return answer;
    }