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

 

문제링크: programmers.co.kr/learn/courses/30/lessons/42885

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

 

풀이

 

people을 가벼운 사람 -> 무거운 사람 순서대로 정렬한 뒤, 보트에 탈 수 있는 (가장 가벼운 사람, 가장 무거운 사람)의 조합을 찾았다. 남아있는 사람들 중 가장 가벼운 사람과도 함께 보트에 타지 못하면 그 사람은 무조건 혼자 보트에 타야 된다. 

 

light: 남아있는 사람들 중 가장 가벼운 사람

heavy: 남아있는 사람들 중 가장 무거운 사람

 

1. people[light] + people[heavy] <= limit    // 두 사람이 같이 보트에 탈 수 있을 경우

   light와 heavy를 같이 보트에 태우고, answer에 1을 더한다. 

 

2. people[light] + people[heavy] > limit    // 두 사람이 같이 보트에 탈 수 없는 경우

   heavy 혼자 보트에 태우고, answer에 1을 더한다. 

 

light >= heavy 가 될 때까지 1, 2를 계산한다. 마지막에 light == heavy 라면 한 사람이 남아있다는 뜻이므로 answer에 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 light = 0, heavy = people.size() - 1;
 
    while(light < heavy) {
        if(people[light] + people[heavy] <= limit) {
            light++;
            heavy--;
            answer++;
        }
        else{
            heavy--;
            answer++;
        }
    }
 
    if(light == heavy) answer++;
 
    return answer;
}

테스트 결과

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)