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

 

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결방법

 

탐욕법. 탐욕 알고리즘 (Greedy Algorithm) 

투 포인터 (Two Pointer)

---

 

 

처음 시도한 코드 - 시간 초과 및 몇 개의 테스트 케이스 실패

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.rbegin(), people.rend());
    int weight = 0;
    
	for(int i=0; i < people.size(); i++)
	{
        weight = 0;
 
        if (people[i] == 0) continue;
        else
        {
            weight += people[i];
            people[i] = 0;
 
            for (int j = people.size()-1; j > i; j--)
            {
                if (weight + people[j] <= limit)
                {
                    weight += people[j];
                    people[j] = 0;
                }
            }
            answer++;
        }        
	}
    
    return answer;
}

가장 무거운 사람 + 가장 가벼운 사람 조합으로 보트에 타게 했다.

 

시간초과 및 몇 개의 테스트 케이스 실패

---

 

정답 코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> people = {70, 50, 80, 50};
 
int solution(vector<int> people, int limit) {
    int answer = 0;
 
    // 무게에 따라 사람들을 정렬
    sort(people.begin(), people.end());
 
    // 두 포인터 left와 right를 초기화
    int left = 0;
    int right = people.size() - 1;
 
    // left 포인터가 right 포인터와 같아지거나 교차할 때까지 반복
    while (left <= right) {
        // 가장 가벼운 사람과 가장 무거운 사람의 무게가 limit 이하라면,
        // 두 사람을 같이 구출할 수 있으므로 left 포인터를 한 칸 오른쪽으로 이동시킨다.
        if (people[left] + people[right] <= limit) {
            left++;
        }
 
        // 가장 무거운 사람이 구출되었으므로 right 포인터를 한 칸 왼쪽으로 이동시킨다.
        right--;
 
        // 구출한 사람 수를 증가
        answer++;
    }
 
    //구출한 사람 수를 반환
    return answer;
}
 
int main() {
    cout << solution(people, 100);
 
    return 0;
}

 

가장 가벼운 사람과 가장 무거운 사람을 참조하는 두 개의 포인터를 사용

 

---