프로그래머스 레벨2 <구명보트> C++ 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/42885

(문제 링크)

프로그래머스

 

흥미로운 문제였습니다. 정확성과 효율성 두개로 테스트케이스가 나뉘어져있고, 따로 채점이 되는 문제였습니다.

제 풀이는 두개입니다. 첫번째 풀이에서는 정확성 TC는 다 맞았지만, 효율성 TC가 전부 틀렸습니다. 두번째 풀이에서는 정확성과 효율성 TC 모두 맞았습니다.

 

일단 먼저 처음 이 문제를 접했을때 들었던 생각은 정렬이었습니다. 무게별로 정렬을 해야겠다는 생각이 자동반사처럼 들었습니다. 그리고 무거운 무게부터 시작해서 두명을 실을 수 있는지 확인해야겠다고 생각했습니다. 무거운 무게부터 최대한 꽉꽉 채우는 것이 보트를 최대한 덜 사용할 수 있는 방법입니다. 더 가벼운 사람을 묶어 태운다면 거기서 오는 무게 로스가 발생하기 때문에 최적의 답이 되기는 어렵습니다.

 

그렇게 가장 무거운 무게부터 탐색하면서 두명을 태울수 없다면 홀자 태우고, 두명을 태울 수 있다면 두명을 태우도록 코드를 짜봤습니다. 이미 보트에 태운사람은 표시를 해야하기 때문에 최대무게를 넘는 300kg으로 변경해주고, 300kg을 상위 for문에서 만나면 continue하도록 구현해봤습니다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool cmp(int a, int b)
{
    return a < b;
}
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end(), cmp);
 
    int idx = people.size() - 1;
    // 50 50 70 80
    for (int i = idx; i >= 0; i--)
    {
        int tmp1 = people[i];
        if (tmp1 == 300)
            continue;
 
        for (int j = i - 1; j >= 0; j--)
        {
            int tmp2 = people[j];
            if (tmp1 + tmp2 <= limit)
            {
                people[j] = 300;
                break;
            }
        }
        answer++;
    }
 
    return answer;
}
 
// 위 코드는 정확성테스트 모두 통과. 효율성 테스트에서 모두 실패(시간초과)
 

 

위 코드로 효율성 테스트에서 전부 시간초과가 나서 코드를 다시 짜야겠다고 생각했습니다. 그 때 자연스럽게 투포인터가 떠올랐습니다. 위 코드의 2중 for문의 구조가 투포인터랑 유사했고, 결국 전부 탐색하지 않으면서 최소한의 탐색으로 답을 골라내는 방법은 투포인터 밖에 없다는 생각이 들었습니다. 

 

left,right를 0과 마지막인덱스로 초기화 시켜주고 가장 무거운 무게 + 가장 가벼운 무게를 했을때, 둘다 태울 수 있다면 태우고 left++, right--를 해줍니다. 만약 둘다 태울 수 없다면 right--를 통해 맨뒷사람만 태우게끔 코드를 구현해봤습니다. 이렇게 풀이한 뒤, 정확성과 효율성 모든 TC에 정답을 맞을 수 있었습니다. 그런데.. 블로그에 이렇게 정리하면서 든 생각인데, 만약 가장 무거운 무게 + 가장 가벼운 무게를 했을 때, 여유가 남아서 조금 더 무거운 무게를 실을 수 있다면 그렇게 하도록 처리를 해야, 최소한의 구명보트의 갯수를 세는 완벽한 해답이 될 것같다는 생각이 들었습니다. 이 부분에 대해서는 조금 더 깊게 고민을 해봐야 할 것 같습니다..!

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool cmp(int a,int b)
{
    return a<b;
}
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end(),cmp);
    //투포인터로 하면 시간초과 안날거같음.
    //두번째 풀이
    
    int left = 0;
    int right = people.size()-1;
    //50 50 60 70 80
    while(left<=right)
    {
        int tmp = people[left] + people[right];
        
        if (tmp <= limit)
        {
            left++;
            right--;
            answer++;
        }
        else
        {
            right--;
            answer++;
        }
    }
    
    return answer;
}