[프로그래머스] 2단계 - 구명보트

문제 설명

무인도에 갇힌 사람들을 무게 제한과 탑승 인원이 최대 2명인 구명보트를 이용해서 구출하려고 할때, 최대한 적게 사용하는 구명보트의 수 return

 

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

프로그래머스

 

문제 풀이법

투 포인터를 활용하여 문제를 풀었다

 

문제에 함정이 있는데, 하나는 각 사람의 몸무게는 40kg이상이고, 구명보트의 무게 제한은 40kg라는 것이다

처음에는 잘못읽고 몸무게가 40kg이 아닌 사람이 있다는 것으로 오해해서 틀렸고, 구명보트의 최대 인원이 2명이라는 것도 못봐서 16번 테스트케이스부터 틀렸다

 

이 함정들을 조심하면서 문제를 풀어야한다(나만 함정이라고 느낄 수 있다)

 

우선 사람들의 몸무게가 있는 vector를 오름차순으로 정렬 한 뒤에, 각각 vector의 처음과 끝의 인덱스를 가리키는 변수를 둔다

start와 end로 명명했다

 

각 포인터가 서로 겹치지 않는 동안만 반복문을 지속하는데, 3가지 분기가 있다

1. people[start] + people[end] > limit

• vector의 처음과 끝의 값을 더한 값이 limit보다 클 때
• 이 경우는 people[end]만이 구명보트에 탈 수 있으므로, answer에 1을 더하고 end를 1을 줄였다
• end를 1 줄였다는 의미는 vector의 끝을 가리키는 곳을 갱신한다는 뜻이다

2. people[start] + people[end] == limit

• vector의 처음과 끝의 값을 더한 값이 limit와 같을 때
• 이 경우는 맨 처음과 끝 사람 2명이 보트에 탈 수 있다는 의미로, answer에 1을 더하고, start를 1을 더하고, end를 1을 줄였다

3. people[start] + people[end] < limit

• vector의 처음과 끝의 값을 더한 값이 limit 보다 작을때
• 이 역시도 2번째와 같은 동작이다
• 다만 이것을 따로 나눈 이유는, 앞서 말했듯이 보트에 탈 수 있는 최대 인원이 2명이라는 것을 모르고 이 단계에서 또 다른 처리를 해주었기 때문이다 (블로그를 쓰다가 깨달았다.... 역시 문제를 풀고나서 해설을 써야한다...)
• 사실상 2번과 3번을 하나로 합쳐도 된다

 

마지막에 start와 end가 서로 같은 경우에는 보트에 타지 못한 1명이 남아있다는 뜻이므로 answer에 1을 더해준다

 

소스 코드

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

using namespace std;

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