프로그래머스 - 구명 보트

레벨 체크 2번째 문제였다. 그리디로 하면 될거같다는 생각을 하고 구현을 하다가 시간을 다 써버렸다.. 이게 앞 문제보다 쉬웠을거 같은데 아쉽다. 15점 받고 끝난 코드가 다음과 같다. 

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    //그리디하게, 그냥 정렬 작은거부터해서 더해가면서 작은애들이랑 잴 무거운애들 묶기. 만약 초과하면 그 전까지만 묶어서 보내고 cnt 증가
    int cnt =0 ;
    sort(people.begin(), people.end(), greater());
    int front = 0; int tail = people.size() - 1;
    while(front < tail)
    {
        if (people[front] + people[tail] <= limit)
        {
            front+=1;
        }
        tail-=1;
        cnt++;
    }
   answer = cnt;
    if (front >= tail) answer++;
    return answer;
}

이거 정말 조금만 더 고치면 되는 문제였는데 정신도 없고 시간도 없어서 못고쳤다. 정말 아쉽다!!

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    //그리디하게, 그냥 정렬 작은거부터해서 더해가면서 작은애들이랑 잴 무거운애들 묶기. 만약 초과하면 그 전까지만 묶어서 보내고 cnt 증가
    int cnt =0 ;
    sort(people.begin(), people.end());
    int front = 0; int tail = people.size() - 1;
    while(front < tail)
    {
        if (people[front] + people[tail] <= limit)
            front+=1;
        tail-=1;
        cnt++;
    }
    if (front == tail)
        cnt++;
    answer = cnt;
    return answer;
}

이게 맞는 풀이인데, front 를 증가, tail 은 감소시켜주는, 즉 한번에 두명을 태우는 일이 일어나게 되고 while이 끝나면 문제가 생긴다.. 이건 한두번 테스트케이스를 출력해보고 마지막의 front와 tail 값을 보면 쉽게 알아챌 수 있다. 좀 더 앞문제에서 시간을 줄였다면 풀 수 있었을 것 같다.

 

문제를 그리디하게 해결하면 되겠다는 생각과, 가벼운애들끼리 먼저 묶어서 보내는것과 가벼운거+무거운애 를 묶는것 중 어느 방법이 더 좋은 방법일 지 고민 후 맞는 방식을 택한다면 충분히 해결 가능한 문제였을 것 같다!

 

조병화 고생했다!

 

순위 20800등