[Lv2]구명보트(C++)

1. 문제

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

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

2. 접근 방법

1) "한 보트엔 최대 2명만 들어갈 수 있다." 라는 점에서 greedy 접근 방식을 생각했다.

( 만약 한 보트에 최대 인원이 정의되어있지 않았다면 DP로 풀어야 했는데, 최대 2명이므로 가장 무거운 사람 + 가장 가벼운 사람을 한쌍으로 묶으면 된다. )

 

2) 사람을 무게 순으로 정렬시킨 후, (가장 무거운 사람(people.back()) + 가장 가벼운 사람(people[0]) > 보트 무게 제한)이면 무거운 사람은 혼자 타게 하고, 만약 무게제한보다 가벼우면 둘을 함께 태운다. 그 다음으로 무거운 사람과 가벼운 사람의 합을 구하는 방식을 반복한다.

 

3. 실수했던 부분 & 처음 알았던 부분

1) erase()는 오래 걸린다.

- 처음에는 다음과 같은 방식으로 풀었는데, 효율성에서 시간 초과가 났다.

while(!people.empty()) {
     	if(people.size() != 1 && (people.back() + people.front()) <= limit) {
            people.pop_back();
            people.erase(people.begin());
        }
        else people.pop_back();
        answer++;

아무래도 가장 앞의 것을 erease()하면 벡터 내 값들이 모두 앞으로 당겨야(?) 하므로, 시간이 오래걸린 것 같았다. 따라서 erase()말고 다른 방식으로 구현해야 했다. 생각해 낸 방법이 지우지 말고 확인만 하자! 였다.

 

- 정렬 벡터의 가장 왼쪽(가장 가벼운 사람) -> 오른쪽 으로 가는 iterator와 가장 오른쪽(가장 무거운 사람) -> 왼쪽으로 가는 iterator 두 개를 사용해서 값을 확인했다.

 

- 비교 종료조건 : while()문의 !people.empty() 조건을 없애는 대신 s(왼쪽 iterator) <= e(오른쪽 iterator)가 되는 순간까지로 바꾸었다.

 

- 여기서 s <= e를 해야 할지, s < e로 해야할 지 고민했는데, 어쨌든 하나가 남았다면 무조건 혼자서 타야 하므로 answer++을 해야 하는 경우이므로 이 문제에선 s<=e로 해도 되었다.

 

2) container 구조체는 if문 조건절에 요소 개수를 확인하자.

- 특정 값이 있는지 확인하려면 container안에 값이 있는지 +  만약 두 값의 합을 구한다면 구조체 내 요소 개수가 2개 이상인지  같은 조건을 확인해야 한다!!

 

4. 코드

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

using namespace std;

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