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

문제 링크

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

 

 

 

풀이

"처음에 어떻게 태우지?"

하다가 구명보트는 2명이 제한이라는 것을 발견하고 바로 풀었다.

deque을 이용하여 pop_front()와 pop_back()을 유용하게 쓰며 진행

대신, 처음에 정렬에 대해서는 vector로 정렬하고 역방향 반복자를 이용해 내림차순으로 정렬하였다.

(deque은 조회에 대해서는 느리다구 한다, 대신 앞, 뒤로 pop이나 push가 용이하다)

 

// init

1. people 벡터 컨테이너를 역방향 반복자를 이용해 내림차순으로 정렬

(오름차순도 상관없다)

2. deque 선언(복사 생성자 이용)

 

// process

반복문(덱이 빌 때까지)

{

    먼저, 구명보트 개수(answer) 증가 --- 나중에 증가시키면 조건문 세우기가 더 까다로워질까봐 미리 증가

    현재 무게(지역 변수: cur)에 [제일 무거운 사람의 무게] 할당 및 pop()

    만약, 덱이 비었을 경우 break(한 명 남았을 때, pop했을 수도 있으므로)

    현재 무게(cur)에 [제일 가벼운 사람의 무게] 추가

    만약, 무게 초과면 continue; (바로 다음 횟수로 이어지도록)

    아니면 pop()

}

 

 

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

using namespace std;

// 한 번에 최대 2명씩, 무게 제한
// 구명보트를 최대한 적게 사용하여 모든 사람 구출

// 사람들의 몸무게를 담은 배열 people
// 무게 제한 limit

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    // init
    sort(people.rbegin(), people.rend());           // 내림차순 정렬(역방향 반복자 이용)
    deque<int> dq(people.begin(), people.end());        // 덱 선언(복사 생성자 이용)
    
    // process
    while(!dq.empty()){
        answer++;           // 구명보트 개수 증가
        int cur = dq.front();       // 현재 무게는 제일 무거운 사람 무게
        dq.pop_front();
        if(dq.empty()) break;       // 갇힌 사람 없을 경우 탈출
        cur += dq.back();
        if(cur>limit) continue;    // 제일 가벼운 사람 무게를 더해 limit 초과면 continue
        dq.pop_back();
    }
    
    return answer;          // 구명보트 개수 최솟값 리턴
}