프로그래머스 코테 연습 : 구명보트

문제 설명

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

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

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

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

제한사항

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

입출력 예

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

어우 근데 이거 색 왜이렇지

---

문제 설명

간단하게 문제를 설명하자면 보트에 두명밖에 못타는데 무게제한이 있어 최소한으로 건널수 있게 해주는 ..그런 문제다. 무게 제한은 limit라고 표현하고 사람의 무게는 people 배열로 들어가게 된다.

​

접근

문제를 볼 때 최소한이라는 힌트를 보고 바로 그리디 라는 감을 찾았다. 최소라는 말만 보면 대부분 그리디는 맞는듯..BFS는 빠르게 찾을수 있으니 아니고 문제 유형이 딱 그렇다고 생각했다.

​

솔직히...좀 많이 쉬웠다.

​

가장 처음 든 생각은 가장 작은 것과 가장 큰 것을 더하면, 그게 최적이 아닐까?라는 생각이다. 가장 작은 것과 가장 큰것을 더했을 때 limit을 넘지 않으면 나머지도 합치면 다 안 넘을거기 때문에... 여기서 반대로 생각하면 가장 작은 것과 가장 큰 것을 더했을 때 limit을 넘는다면 가장 큰 것은 뭘 더해도 limit을 넘기게 될 것이다.

• 실패 코드 1 (오름차순 정렬)

 

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

using namespace std;

vector<int> people;
deque<int> dq;
int limit;

int main()
{
    for(int i = 0; i < 4; i++)
    {
        int a;
        cin >> a;
        people.push_back(a);
    }

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

    for(int i = 0; i < people.size(); i++)
    {
        dq.push_back(people[i]);
    }

    int sol = 0;

    while(!dq.empty())
    {          
        if(dq.front() + dq.back() <= limit)
        {
            dq.pop_back();
        }    
        dq.pop_front();
				sol++;
    }

    cout << sol;
}

예제를 통해 생각해 보자. people 은 [70, 50, 80, 50] 와 같이, limit = 100 으로 들어올 것이다. 만약 오름차순 정렬을 한다면, 50, 50, 70, 80 과 같이 정렬 될 것이다. 80은 가장 작은 수인 50과 더했을 때 limit인 100을 넘기게 된다. 그렇다면 몸무게가 80인 사람은 혼자서 보트 하나를 써서 건너야 할 것이다. 그러나 50 과 50이 만날 때는 어쨌든 1번만에 건널 수 있으므로 둘다 빼낼 수 있다.

​

코드 풀이

people로 들어온 수들을 내림차순 정렬 해준다.(사실 오름차순일 때 솔루션을 생각해내지 못해서 반대로 생각해 봤다.)

예제 케이스를 볼 때 people 은 80, 70, 50, 50으로 정렬될 것이다. 그렇다면, 양 끝의 두 수를 더한다. 더할 때 limit(100)보다 큰 수가 나온다면 80은 어느수와도 어울리지 못하기 때문에, 80만 빼내고 count를 1 증가 시켜준다. 왜냐면 80인 사람은 보트를 혼자 쓸 것이기 때문에. 그렇다면, 80이 빠진 70, 50, 50에서 70또한 똑같은 프로세스를 거칠 것이다. 70도 빠지고 count를 1증가 시켜준다. 그러나, 50과 50은 100을 넘기지 않으므로, 둘 다 보트를 한번에 쓸 수 있다. 양 방향 모두를 빼고 count를 1을 증가시키는 것이다.

​

즉, 그렇다면 양방향 모두 값을 뺄 수 있어야 한다는 뜻이기도 하다. 이렇기 때문에 나는 자료구조를 deque를 선택했다.

​

• 정렬

bool compare (int a, int b)
{
    return a > b;
}

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

compare 함수를 통해 sort를 오름차순이 아닌 내림차순으로 정렬해준다.

​

• deque에 people 배열 삽입

    deque<int> dq;
    for(int i = 0; i < people.size(); i++)
    {
        dq.push_back(people[i]);
    }
    
    int answer = 0;

• 핵심 로직

while(!dq.empty())
    {
        int first = dq.front();
        answer++;
        dq.pop_front();
        
        if(!dq.empty() && (first + dq.back() <= limit))
        {
            dq.pop_back();
        }
    }
    return answer;

deque가 빌 때까지 계속 반복 해준다. 내림차순 정렬한 첫 값을 first변수에 넣고, answer을 추가한다. 그리고 pop을 시킨뒤, dq가 비었지 않으면서, first 와 deque의 맨 끝값을 더했을 때 limit 을 넘지 않으면 끝값도 같이 pop해준다.

​

​

전체 코드

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

using namespace std;

bool compare (int a, int b)
{
    return a > b;
}

int solution(vector<int> people, int limit) 
{
    deque<int> dq;
    
    sort(people.begin(), people.end(), compare);
    
    for(int i = 0; i < people.size(); i++)
    {
        dq.push_back(people[i]);
    }
    
    int answer = 0;
    while(!dq.empty())
    {
        int first = dq.front();
        answer++;
        dq.pop_front();
        
        if(!dq.empty() && (first + dq.back() <= limit))
        {
            dq.pop_back();
        }
    }
    return answer;
}

느낀 점

원래는 오름차순을 생각했다. 근데 풀다 보니 오름차순 어떻게 빼지...이러다가 그냥 멍청하게 안되는거 같은데 그냥 내림차순 해야겠다 이렇게 생각했는데 ㅋㅋㅋㅋㅋㅋ deque를 아는지 물어보는 문제였던것 같다...

다만 내가 한달동안 알고리즘 안햇더니 머리가 굳어버려서 하...하하 멍청해졌네..