[프로그래머스] 구명 보트 (C++) - Lv.2

문제

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

프로그래머스

 

개요

문제를 잘못 이해한 채로 풀이를 시작해서 생각보다 굉장히 애를 먹은 문제이다.

한 번에 최대 2명씩 탈 수 있다는 문제 조건에 유의하자.

 

정답 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int ans = 0; // 필요한 보트 개수
    sort(people.begin(), people.end()); // 오름차순 정렬
    int len = people.size();
    int start = 0, end = len - 1;
    
    while(start <= end){
        // 가장 가벼운 사람과 가장 무거운 사람 무게 합쳐도 limit 이하인 경우
        if (people[start] + people[end] <= limit){
            start++; // 남아있는 사람 중 가장 가벼운 사람 탑승 
        } 
        end--; // 남아있는 사람 중 가장 무거운 사람 탑승
        ans++; // 필요한 보트 개수 증가
    }
    return ans;
    
}

 

일단, people 배열을 오름차순으로 정렬했다.

 

그리고 투포인터 방식을 사용했다.

start는 맨 앞에서부터, 즉 남아있는 사람 중 가장 가벼운 사람을

end는 맨 뒤에서부터, 즉 남아있는 사람 중 가장 무거운 사람을 가리키는 변수이다.

 

구명 보트에 사람이 탑승하는 경우는 크게 2가지가 있다.

 

(1) 가장 가벼운 사람과 가장 무거운 사람이 함께 탑승하는 경우

즉, 수식적으로 설명하면 people[start] + people[end] <= limit 인 경우를 의미한다.

이 때, start++를 통해 가장 가벼운 사람 탑승하고, end--를 통해 가장 무거운 사람도 탑승한다.

그리고, ans++를 통해 구명 보트 개수가 하나 증가한다.

 

(2) 가장 무거운 사람 혼자 탑승하는 경우

즉, 남아있는 사람 중 (가장 가벼운 사람 + 가장 무거운 사람) 무게가 limit을 초과하는 경우이다.

이 경우에는 가장 무거운 사람 혼자 보트에 탑승해야 한다.

가장 가벼운 사람이랑도 같이 타지 못하기 때문에 다른 누구와도 같이 탑승할 수 없는 것이다.

이 경우에는 end--를 통해 가장 무거운 사람만 탑승하고, ans++를 통해 구명 보트 개수가 하나 증가한다.

 

위의 정답 코드는 정말 간략하게 작성한 코드이고, 정말 직관적으로 작성한 투 포인터 코드는 다음과 같다.

while(start <= end){
    if (people[start] + people[end] <= limit){
        start++;
        end--;
        ans++;
    }
    else{
    	end--;
        ans++;
    }
}

 

깨달은 점

일단, 문제가 길더라도 시간에 쫓겨 문제 조건을 제대로 인지하지 못하는 일은 없어야겠다는 깨달음을 얻었다.

 

그리고, 기존에는 start, end 모두 맨 앞에서 시작하는 투포인터 방식만 사용해봤었는데,

start는 맨 앞에서부터, end는 맨 뒤에서부터 시작하는 투포인터 방식이 더 직관적이고 쉽다는 것도 알게 되었다.