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

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end(),greater<>());
    
    int begin = 0;
    int end = people.size()-1;
    
    while(begin<end)
    {
        if(people[begin]+people[end]<=limit)
        {
            begin++;
            end--;
        }
        else
            begin++;
        answer++;
    }
    
    if(begin==end)
        answer++;
    
    
    return answer;
}

 

가벼운 사람과 젤 무거운 사람을 묶어 보내는 게 답인가?

그러다 2명을 묶어 보낼 수 있는데 1명만 보내서 보트 낭비하는 경우는 안 생기는가?

가장 무거운 사람과 함께 태울 수 있는 사람이 여러 명이면 나중을 위해

무거운 사람을 태우는 것이 맞지 않나??라고 생각했는데

 

내림차순으로 정렬된

x1 x2 x3x4가 있다고 하면 

 

x4<=limit

x2+x3>limit
x2+x4<=limit ?? x4는 x3보다 무거운데?

모순이 있는 것 같다. 그래서 가장 가벼운 애를 태우는 게 맞는 것 같다.

 

틀린 코드

1. 그냥 가벼운 애들을 우선적으로 담아 태워 보내면 보트를 최소로 할 수 있었을 것 같았다.

하지만 틀린 풀이였다.

아래의 테스트 케이스를 보자.

[30, 40, 50, 60]

limit=100일때 

가벼운 애들은 먼저 태우면 3번이 걸린다. 하지만 60+40, 50+30으로 2번이 걸리는 방법이 있다.

가벼운 애들을 먼저 태우다 무거운 사람을 태워 limit를 꽉꽉 채울 수 있음에도 비효율적으로 보트를 운영한 것이다.

 

2. vector에서 임의의 위치에 원소를 추가하거나 삭제할 때 O(n)이라 아래의 코드는 시간 초과

int answer = 0;
    sort(people.begin(),people.end(),greater<>());
    
    while(people.size()>1)
    {
        if(people[0]+people[people.size()-1]<=limit)
        {
            people.erase(people.end()-1);
            people.erase(people.begin());
        }
        else
        {
            people.erase(people.begin());
        }
        answer++;
    }
    
    if(people.size()==1)
        answer++;