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

구명보트

 

 

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 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

 

시작 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    return answer;
}

 

나의 풀이

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

using namespace std;

int solution(vector<int> people, int limit) {
    // people : 몸무게, limit : 무게 제한
    // 구해야 하는 것 : 구명보트 갯수 최솟값
    // 투 포인터
    
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    int left = 0;
    int right = people.size() - 1;
    
    while (left <= right)
    {
        if (people[left] + people[right] <= limit)
        {
            // 가장 가벼운 사람과 무거운 사람을 한 보트에 태움
            left++;
        }
        // 가장 무거운 사람은 항상 보트에 태움
        right--;
        answer++; // 보트 한 대 추가
    }
    
    return answer;
}

 

코드 분석

주어진 int형 벡터 people을 정렬합니다. 이후 int형 변수 left와 right를 선언해주고 right는 people크기의 -1로 초기화 시켜줍니다. while문을 통해 left가 right보다 작거나 같으면 안에서 계속 실행하도록 해주고, 그 안에서는 if문을 통해 people의 left인덱스 위치의 값과 right인덱스 위치의 값을 더한 값이 limit보다 작거나 같다면 left를 증가시키고, if문 이후에는 right를 감소, answer를 증가시키도록 합니다. 모든 과정이 종료되면 answer 값을 리턴하며 종료합니다.

 

풀이 설명

위 문제에서 요구하는 것은 구명보트를 최대한 적게 사용하여 모든 사람을 구출하는 것입니다. 최종적으로 구해야 하는 값은 최소한으로 사용된 구명보트의 갯수입니다. 위 소스코드는 작성된 코드의 양은 매우 적지만, 투포인터 개념이 적용되어 있습니다.

 

투포인터(Two Pointers) 기법은 배열이나 리스트 같은 순차 자료구조를 효율적으로 탐색하거나 특정 조건을 만족하는 구간을 찾을 때 사용하는 알고리즘 기법입니다. 이 기법은 두 개의 포인터(변수)가 같은 배열 위에서 이동하면서 문제를 해결합니다. 일반적으로 투포인터는 다음 두 가지 방식으로 사용됩니다 

 

• 정렬된 배열에서 특정 조건을 찾는 경우 (두 포인터 이동)
• 구간 합 또는 슬라이딩 윈도우 형태로 활용 (연속 부분 합 문제)

이번 문제는 첫번째인 정렬된 배열에서 특정 조건을 찾는 경우를 나타냅니다. 이제 코드를 살펴보겠습니다.

 

먼저 배열을 정렬하면서 코드가 시작됩니다. 그리고 left와 right로 양쪽에서 사용할 포인터를 지정해 생성해줍니다. 서로 배열의 양쪽 끝에서 시작위치를 잡아줍니다. 이때 배열이 정렬되어 있으므로, left는 가장 가벼운 사람, right는 가장 무거운 사람을 가리킵니다. While문은 양쪽 포인터가 이동할 때 종료조건을 두 포인터가 만날때까지로 설정하였습니다. left는 점점 증가하고, right는 점점 감소하면서 둘 다 가운데를 향해 움직이기 때문에 두 포인터가 만나고 난 이후에 While문의 조건을 만족하지 않아 종료됩니다.

 

While문에서는 양쪽 포인터 위치에 있는 몸무게 값의 합이 limit보다 작거나 같은지 체크하여 맞다면 left를 움직이도록 합니다. if문을 만족하지 않는다는 것은 최소값과 최대값의 합으로 한 보트에 태울 수 없다는 뜻이므로, 최대값의 몸무게를 가지는 친구는 무조건 보트를 사용하여 태운다는 뜻으로 right를 감소시키고, answer(보트)를 증가시키는 것입니다. 이제 마지막으로 위 방식을 예제에 적용하여 실행해보겠습니다.

 

입출력 예1번의 people을 정렬하면 [50, 50, 70, 80]이고, people[left]는 50, people[right]는 80입니다. if문을 만나면 만족하지 않으므로 right를 감소시키고 answer는 1이 됩니다. 다음 회차의 while문을 실행하면 50과 70으로 똑같이 만족하지 않아 right감소, answer는 2가 되고, 다음 회차는 50, 50이 되어 if문을 만족합니다. left를 증가시키고, 똑같이 right를 감소시킨 뒤 answer는 3이 됩니다. 현재 left는 1(50), right는 0(50)이 되었고, left가 더 커지게 되어 while문을 만족하지 않아 종료됩니다. 최종적으로 완성된 answer값 3을 리턴하며 코드는 종료됩니다.

 

<NEXT>

이번에는 정답률 70%의 탐욕법 카테고리의 문제 "구명보트"를 풀어보았습니다. 다음에는 연습문제 "멀리뛰기"를 다뤄보도록 하겠습니다. 감사합니다.