[2023년 11월 22일]구명보트(25분)

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

구현 아이디어 15분 구현 10분

풀이

처음에는 while(lp < rp)였고 이 경우 lp와 rp가 같을 수 없기 때문에 if(lp == rp) sum /= 2;가 없었다. 그리고 주석 부분인 if(people.size() % 2) ++answer;을 넣어 줬는데 people이 홀수일 경우 남는 하나를 세지 않기 때문이었다.

그러나 반례가 존재했다. people = {10, 10, 10, 10}, limit = 10인 경우 기대값은 4인데 3이 출력된다.

아래는 채점을 통과한 풀이이다.

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    int lp = 0, rp = people.size() - 1;
    int lp_people, rp_people, sum;
    
    while(lp <= rp)
    {
        lp_people = people[lp];
        rp_people = people[rp];
        sum = lp_people + rp_people;
        
        if(lp == rp) sum /= 2;
        
        if(limit < sum)
        {
            ++answer;
            --rp;
        }
        else if(limit >= sum)
        {
            ++answer;
            --rp;
            ++lp;
        }
    }
    
    // if(people.size() % 2) ++answer;
    
    return answer;
}