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

문제링크

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

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

 

문제난이도

Level 2

 

문제풀이

1. 몸무게를 담고 있는 벡터(people)를 오름차순 정렬해준다

2. 가장 가벼운 몸무게(=head)와 가장 무거운 몸무게(=tail)을 가리키는 인덱스 설정한다

3. head가 tail과 같은 경우(같은 사람을 가리키는 것)이거나 head가 더 큰 경우(모든 경우 탐색완료)

   탐색을 종료한다

3-1. head와 tail이 같은 경우, 같은 사람을 가리키는 것이므로 보트이동 1획 발생

      탐색종료

3-2. head와 tail의 몸무게 합 <= limit인 경우, 보트이동 1회 발생

      다음 사람 탐색을 위해 head+1, tail+1

3-3. head와 tail의 몸무게 합 > limit인 경우, 보트이동 1회 발생

       - 현재 이동하지 않은 사람중 가장 무거운 사람은 tail이 가리킨다

       - 현재 이동하지 않은 사람중 가장 가벼운 사람은 head가 가리킨다

       - 둘의 합이 limit을 넘는 경우, tail이 가리키는 사람은 이동하지 않은 어떠한 사람들과도

         몸무게 합이 limit이 넘기 때문에 보트이동을 혼자 한다

       - 따라서 보트이동 1회가 발생하고 tail이 가리키는 사람만 변동이 있다

 

 

소스코드 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
 
    sort(people.begin(), people.end());    //오름차순 정렬
    int head = 0;
    int tail = people.size() - 1;
 
    //head와 tail이 가리키는 인덱스가 같거나 head의 index가 더 큰경우, 탐색 종료
    while (head <= tail) {
 
        //head와 tail의 인덱스가 같다면, 동일한 사람인 경우이다
        //이런 경우, 한명의 사람을 구명보트에 태워 보낸다
        //더 탐색할 사람이 없으므로 종료
        if (head == tail) {
            answer++;
            break;
        }
 
        //head와 tail이 가리키는 사람들의 몸무게 합이 limit보다 작거나 같은 경우
        //구명보트 이용 +1 증가
        //현재 가리키는 사람은 이동이 완료되 었으므로 다믕 사람 탐색을 위해
        //head는 1증가, tail은 1감소
        if (people[head] + people[tail] <= limit) {
            answer++;
            head++;
            tail--;
        }
        else {
            //두명의 몸무게 합이 limit보다 큰 경우,
            //몸무게가 큰 쪽을 가리키는 tail-1
            //몸무기가 큰 쪽은 혼자 구명보트 이용을 해야하므로 answer + 1
            answer++;
            tail--;
        }
    }
 
    return answer;
}