[Programmers]탐욕법 > 구명보트

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

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

 

문제를 푸는 방법 자체는 어렵지 않았다. 그런데 아무리 도전해도 계속 효율성에서 시간초과가 나서 ㅠㅠ 뭐가문제인지 모르겠어서 구글 검색을 했다.

현재 인원 중에서 제일 무거운 사람과, 제일 가벼운사람을 태울 수 있으면 같이 태우고,

태울 수 없으면 제일 무거운 사람만 혼자 태운다.

-> 제일 가벼운 사람을 못태우므로 나머지 사람들도 모두 함께 탈 수 없음

 

1.  people을 내림차순으로 정렬

2. front = 0부터 시작, end는 people의 마지막인덱스 people.size()-1 

3. 제일 큰 (제일 앞에 있는) people[front]를 boat안에 넣고, boat.back()의 값과 people[end]의 값이 limit이하이면 end--

4. front는 항상 ++

5. front보다 end가 더 작거나 같아질때까지 반복한다.

6. boat의 사이즈가 구명보트의 최솟값이다.

 

투 포인터 방식처럼 front, end 변수를 두고 보트안에 제일 무거운 사람을 태우면 front++, 제일 가벼운 사람도 태울 수 있으면 end--를 하면서 front <= end일때까지 반복한다.

 

 

 

 

 

main포함 코드(c++)

---

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

vector<int> boat;
bool compare(int a,int b){
    return a>b;
}
int solution(vector<int> people, int limit) {
    int answer = 0;
    int front = 0;
    int end = people.size()-1;
    int cnt = 0;
    sort(people.begin(), people.end(), compare);
   
    while (front <= end) {

        boat.push_back(people[front]);
        if (people[front] + people[end] <= limit) {
            boat.back() += people[end];
            end--;
        }
        front++;
    }
    
    answer += boat.size();
    return answer;
}


int main() {

//    vector<int> people = {160, 150, 140, 60, 50, 40};
//    int limit = 200;
    
//    vector<int> people = {80,70,50,50};
//    int limit = 100;
    
//    vector<int> people = {80,70,50};
//    int limit = 100;
    
    vector<int> people = {40,50,60,90};
    int limit = 100;
    
    solution(people, limit);
}

 

---

시도한 테스트케이스

{160, 150, 140, 60, 50, 40} , 200 / 3

{80,70,50,50} , 100 / 3

{80,70,50}, 100 / 3

{40,50,60,90}, 100 / 3