프로그래머스 - 구명보트(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42885

문제 난이도

Lv 2

문제 접근법

그리디 알고리즘이므로 현재, 최선의 해를 찾아 푸는 방식을 떠올렸다.
그리디의 대표적 문제인 거스름돈 알고리즘을 생각하고 이 구조를 생각했다.

근데 이 문제 카테고리가 그리디라는 힌트가 없었으면 시간 꽤 걸렸을 듯 하다..

추가한 라이브러리
algorithm

통과 코드

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

using namespace std;

bool ch[50001];

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end(), greater<int>());
    int min_idx = people.size()-1;
    for(int i=0; i<people.size(); i++){
        int mod = limit - people[i];
        if(ch[i]) continue;
        if(mod >= people[min_idx]){
            ch[min_idx] = true;
            min_idx--;
        }
        answer++;
        ch[i] = true;
    }
    return answer;
}

피드백

한 번에 통과할거란 기대는 없었는데 한 번에 통과해서 놀랐다. 내 코드가 좀 더 복잡한 거 같다. 통과하고 나서 다른 사람 풀이를 확인하는데 내림차순해서 끝과 끝을 비교하는 구조는 비슷하지만 더 깔끔하다. 너무 복잡하게 생각하지 말 것!

for (int i = 0, j = people.size()-1; i <= j; i++) {
        if (people[i] + people[j] <= limit) {
            j--;
        }
        answer++;
    }