[프로그래머스 Level 2] [그리디] 구명보트 (C++)

안녕하세요, 코딩하는 경제학도 쏘코입니다.

여전히 그리디의 굴레에서 벗어나지 못하고 있는 상황입니다...

빨리 여길 탈출하고 다음 단계로 넘어가고 싶은 마음이 굴뚝같습니다.

그러려면 이 문제부터 넘어야겠죠? 바로 설명해보겠습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42885

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

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5

programmers.co.kr

0. 문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

0.0. 제한사항

무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

0.1. 입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

1. 풀이 과정

처음에는 2명의 무게를 더해서 가장 limit에 가까운 친구들부터 빼고, 더이상 2명씩 뺄 수 없을 때 하나씩 빼서 answer를 구하려고 했습니다. 그런데 이 과정에서 2명의 무게를 더해서 가장 limit에 가까운 친구들을 찾는 과정이 쉽지 않았습니다. 이중 for문을 사용해서 문제를 해결해보려고 했지만 이미 뺀 친구들을 따로 처리해 줘야 하는 번거로움과 시간초과 문제가 발생했습니다.

한참을 생각해도 이것보다 더 좋은 아이디어는 없을까 생각하며 질문탭을 보면서 아이디어에 도움을 받았습니다.

제가 생각하지 못했던 부분은 가장 가벼운 친구와 들어갈 수 있는 가장 큰 친구를 찾아서 먼저 구조해도 동일하다는 것이었습니다. 몸무게가 40 50 90인 친구들이 있는데, 140이 들어갈 수 있는 보트가 있다면 물론 50 90이 들어가서 가장 최적에 가깝게 보트를 운용하는 것도 좋지만, 어짜피 횟수에는 차이가 없었습니다. 따라서 같이 못태우는 친구들은 제끼고, 같이 태울 수 있는 경우들을 모아서 짝지어주면 정답을 구할 수 있습니다.

다양한 방법이 있겠지만 저는 people이라는 vector를 그대로 사용했습니다. 가장 무거운 친구의 몸무게를 추출한 후 pop_back으로 빼버리고 가장 가벼운 친구와 몸무게를 더해서 limit를 넘으면 그대로, limit를 넘지 않으면 idx를 앞으로 한칸 땡겨서 2명이 나간 것을 표시했습니다. 이런 방식을 사용해서 idx가 people.size()와 같거나 넘어서는 순간 while문을 멈추고 answer가 반환될 수 있게 만들었습니다. (만일 등호가 들어가면 pop_back으로 뺴버렸는데 그 부분을 people[idx]로 참조하게 됩니다. 따라서 없는 메모리를 참조하게 되며 core dump가 발생하게 됩니다.)

2. 소스 코드

2.0. 정답 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int idx = 0;
    sort(people.begin(), people.end());
    
    while(people.size() > idx){
        int biggest = people.back();
        people.pop_back();
        if(people[idx] + biggest <= limit){
            ++idx;
            ++answer;
        }
        else
            ++answer;
    }
    
    
    
    
    return answer;
}

2.1. 시행착오 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int checkidx[50000] = {0,};
    int nowidx1 = -1;
    int nowidx2 = -1;
    int maxkg = 0;
    int left = people.size();
    while(left != 0){
        for(int i = people.size()-1; i >= 0; --i){
            if(checkidx[i] == 0){
                maxkg = people[i];
                nowidx1 = i;
            }
        }
        for (int i = 0; i < people.size(); ++i){
            if(checkidx[i] == 1)
                continue;
            for (int j = i+1; j < people.size(); ++j){
                if(checkidx[j] == 1)
                continue;
                if(people[i]+people[j] > maxkg && limit >= people[i]+people[j]){
                    nowidx1 = i;
                    nowidx2 = j;
                    maxkg = people[i]+people[j];
                }
            }
            if(nowidx2 == -1){
                checkidx[nowidx1] = 1;
                --left;
                ++answer;
            }
            else{
                checkidx[nowidx1] = 1;
                checkidx[nowidx2] = 1;
                --left;
                ++answer;
            }
        }
    }
    
    
    
    return answer;
}