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

1. 문제이해

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

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

 

사람들의 몸무게를 의미하는 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때,

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 리턴하는 것이 목표이다.

(단, 구명보트에는 한 번에 최대 2명까지 탈 수 있다.)

 

 

 

2. 문제풀이

 

사람들의 몸무게와 구명보트의 무게제한이 주어질 때,

사람들을 모두 구하려면 구명보트가 몇개나 필요한지를 구하는 것이 목표이다.

가장 중요한 점은 구명보트에는 한 번에 최대 2명까지만 탈 수 있다는 점이다.

(필자는 이 조건을 빼먹었다가 꼬박 하루를 고민했다..😭)

 

구명보트의 무게제한을 넘지 않으면서 최대한 많은 사람들을 최소의 구명보트로 구하려면,

2명까지 최대한 탈 수 있는 경우의 수를 생각해야한다.

입출력 예의 첫번째 예시를 보면,

사람들의 몸무게(people)는 [70, 50, 80, 50], 구명보트의 무게제한(limit)은 100이다.

이 경우, 가장 무거운 사람인 80을 먼저 태우면, 나머지 사람들 중 가장 가벼운 사람이 50이므로,

그 누구도 80인 사람과 함께 탈 수 없으므로 80 혼자 보트를 쓰게 된다.

이후 가장 무거운 사람인 70 또한, 가장 가벼운 사람이 50이므로, 혼자 보트를 쓰게 된다.

이후 가장 무거운 사람인 50은, 가장 가벼운 사람이 50이므로 둘이 합쳐 무게제한을 넘지 않으므로 두명이 함께 타게 된다.

이렇듯, 위와 같은 경우 필요한 구명보트의 최솟값은 3개가 된다.

 

위 예제에서 적용한 문제풀이 방법을 그대로 소스코드로 구현해보기로 했다.

위 풀이방법에서 적용한 문제풀이 방법은 다음과 같다.

 

 

1. 사람들의 몸무게(people)를 정렬

 

2.  가장 무거운 사람의 몸무게를 따로 저장후 배열에서 삭제

(아래 3-1, 3-2 의 경우 모두 보트에 타게 되어있으므로 먼저 삭제하고 시작)

 

3. 가장 무거운 사람부터 보트에 태운 뒤, 가장 가벼운 사람의 몸무게를 확인

3-1. 둘이 합쳐 무게제한을 넘지 않는다면, 두명 모두 보트에 탄다.

3-2. 둘이 합쳐 무게제한을 넘긴다면, 무거운 사람만 보트에 탄다.

 

4. 2-2의 경우, 그 다음으로 가벼운 사람을 골라야 하므로 index 지정 후 한칸 씩 옮겨줌

2-1의 경우, 가장 가벼운 사람이 구출되지 않은 것이므로, index는 옮기지 않음

 

5. 가장 무거운 사람을 다시 설정. 가장 무거운 사람은 어떤 경우에서던 보트에 타게 되므로,

이번에도 따로 저장 후 배열에서 삭제하고 3, 4과정 반복

 

6. 2~5과정을 반복하며,

index가 가리키는 값(구출되지 않은 사람중 가장 가벼운 사람의 순서)이 남아있는 사람수보다 크다면 종료

 

 

문제풀이에서 도출해낸 위와 같은 방법에 따라 작성한 코드는 아래와 같으며,

주어진 틀은 아래와 같았다.

 

 

 

3. 소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int index = 0;      // 구출된 사람을 제외하고 가장 적은 몸무게
    int last_person;    // 가장 무거운 사람의 몸무게
    int count = 0;      // 필요한 구명보트의 개수
    
    // 몸무게를 오름차순으로 정렬
    sort(people.begin(), people.end());

    // 가장 가벼운 사람을 가리키는 인덱스보다 남아있는 사람수가 더 적으면 while문 종료
    while(people.size() > index){
        // 가장 무거운 사람은 둘이 타던, 한명 타던 구명보트에 타게됨.
        // while문을 돌때마다 무거운 사람을 초기화해주어야 함.
        last_person = people.back(); 
        people.pop_back();
        
        // 1. 가장 가벼운 사람 + 가장 무거운 사람 <= 무게제한
        //  : 한번에 2명만 탈 수 있고, 둘이 탔기때문에 구명보트 1개 사용 (count++)
        //  : 가장 가벼운 사람이 타버렸으므로, 다음으로 가벼운 값을 찾는다. (index++)
        if(people[index] + last_person <= limit){
            count++;
            index++; 
        }
        // 2. 가장 가벼운 사람 + 가장 무거운 사람 >= 무게제한
        //  : 가장 무거운 사람만 탈 수 있는 경우로, 1명만 타고 구명보트 사용 (count++)
        //  : 그 다음으로 가벼운 값은 찾을 필요없다. 아직 타지 못한 경우이므로.
        else {
            count++;
        }
    }
    
    answer = count;
    return answer;
}

이해를 위해 주석을 비교적 자세하게 적어보았다. (아래 주석없는 코드를 따로 첨부했습니다.😊)

먼저 구출된 사람들을 제외하고 가장 가벼운 사람을 가리키는 index와,

구출된 사람을 제외하고 가장 무거운 사람을 가리키는 last_person,

필요한 구명보트의 개수인 count 변수를 설정해주었다.

 

2. 문제풀이에서 처럼, 먼저 사람들의 몸무게를 정렬해준뒤, while문과 if문을 통해 위 과정을 구현해주었다.

가장 가벼운 사람을 가리키는 index 보다 남아있는 사람수가 더 적으면 while문을 종료하며,

while문을 반복할때마다, 가장 무거운 사람은 어느 경우던지 보트를 타게 되므로,

남아있는 사람들 중 가장 무거운 사람을 따로 저장해주고, 배열에서 삭제해주었다.

 

while문안에는 if문을 통해 3. 가장 무거운 사람부터 보트에 태운 뒤, 가장 가벼운 사람의 몸무게를 확인하고,

 

3-1. 둘이 합쳐 무게제한을 넘지 않는다면, 두명 모두 보트에 탄다.

: 한번에 2명만 탈 수 있고, 둘이 탔기때문에 구명보트 1개 사용 (count++)
가장 가벼운 사람이 타버렸으므로, 다음으로 가벼운 사람을 찾는다. (index++)

 

3-2. 둘이 합쳐 무게제한을 넘긴다면, 무거운 사람만 보트에 탄다.

: 가장 무거운 사람만 탈 수 있는 경우로, 1명만 타고 구명보트 사용 (count++)
      그 다음으로 가벼운 사람은 가장 가벼운 사람이 아직 타지 못했으므로 index 값 증가 X

 

로 경우를 나누어 구현해주었다.

위 과정을 반복하고 나면, 필요한 구명보트의 최솟값(count)이 나오게 되고,

이를 answer에 대입 후 리턴하게 된다.

 

 

주석 없는 코드는 바로 왼쪽 아래의 더보기 확인 바랍니다.😊

<주석 없는 코드>

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int index = 0;      
    int last_person;    
    int count = 0;      
    
    
    sort(people.begin(), people.end());

    
    while(people.size() > index){
        last_person = people.back(); 
        people.pop_back();
        
        if(people[index] + last_person <= limit){
            count++;
            index++; 
        }
        
        else {
            count++;
        }
    }
    
    answer = count;
    return answer;
}

 

 

---

보트에 최대 두명만 탈 수 있다는 조건을 못보고.. 열심히 삽질한 문제였다..

어쩐지 레벨2 치고 너무 어렵더라....