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

11 Oct 2022 in Study on Coding Test

알고리즘을 잘못 짜서 삽질하던 기억이 남아서 작성하는 포스트

정답제출코드

#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());
    
    int index_1 = 0;
    int index_2 = people.size() - 1;
    
    while(index_1 <= index_2)
    {
        if (people[index_1] + people[index_2] <= limit)
        {
            --index_2;
            ++index_1;
        }
        
        else
        {
            --index_2;
        }
        answer++;
    }

    return answer;
}

소스코드 설명

• 제일 효율적인 그리디 알고리즘이 무거운 사람과 가벼운 사람을 한번에 두명씩 같이 태우는 것임.

• 우선 가벼운 순서대로 벡터를 정렬하고 가벼운 사람을 가리키는 index_1과 무거운 사람을 가리키는 index_2를 설정함.

• 가벼운 사람 + 무거운 사람을 태웠는데 한계치를 넘지 않으면 각각 다음 인덱스로 넘어감.

• 한계치를 넘어서는 경우 무거운 사람만 태우고 index_2만 다음 인덱스로 이동함.

• 두 인덱스가 교차할 때 까지 반복함.

삽질한 내용

아래는 내가 삽질했던 코드이다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> people, int limit) {
    
    int answer = 1;
    int capacity = 0;
    int count = 0;
    
    // 원활한 진행을 위해 오름차순 정렬을 한다.
    sort(people.begin(), people.end());
    
    for (int i = 0; i < people.size(); ++i)
    {
        if (capacity + people[i] <= limit && count < 2)
        {
            // 조건이 맞다면 capacity에 인원의 무게를 더함.
            // 그리고 count 인원 추가.
            capacity += people[i];
            ++count;
        }
        
        else
        {
            // capacity에 무게를 더했더니 한계치를 넘어선 경우
            // 혹은 2명을 초과한경우
            // 배의 개수를 추가하고 iter를 이전으로 되돌려놓는다.
            // 그리고 capacity와 count 초기화.
            ++answer;
            --i;
            capacity = 0;
            count = 0;
        }
    }
    
    return answer;
}

요약을 하자면 가벼운 사람부터 순차적으로 태웠다.

만약에 2명의 인원제한이 없었다면 가벼운 사람들부터 태우는 것이 좋았을 것이라 생각하지만, 2명의 인원제한을 간과하여 삽질했던 것 같다.

동료들에게 도움을 구해서 무거운사람과 가벼운사람을 같이 태우라는 힌트를 얻어내었고 맨 위에 있는 코드로 재구성하여 답을 제출하였다.

알고리즘을 잘못 짜서 1시간 동안 맞왜틀의 지옥에 빠지고 삽질을 했던 기억이 인상깊어서 이렇게 포스트를 남긴다.