문제
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
int left = 0;
int right = people.size() - 1;
sort(people.begin(), people.end());
while(left <= right) {
if(people[left] + people[right] > limit) {
right--;
} else {
left++;
right--;
}
answer++;
}
if(left == right) answer++;
return answer;
}
풀이
구명보트에는 2명만이 탈 수 있고 최대한 limit 에 가깝게 맞춰서 보내야하기 때문에 우선 사람들의 몸무게를 오름차순으로 정렬한다. 그 다음, 가장 가벼운 사람과 가장 무거운 사람을 가리키는 두 개의 포인터(left, right)를 선언한다.
만약 두 포인터의 몸무게 합이 limit 를 넘어서면 무거운 사람만 먼저 보낸다. 무거운 사람만 보내는 이유는 가벼운 사람은 다음 무거운 사람과 같이 갈 수 있는 확률이 존재하기 때문이다.
만약 두 포인터의 몸무게 합이 limit 이하라면 둘 모두 보내게 된다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
int left = 0;
int right = people.size() - 1;
sort(people.begin(), people.end());
while(left <= right) {
if(people[left] + people[right] > limit) {
right--;
} else {
left++;
right--;
}
answer++;
}
if(left == right) answer++;
return answer;
}
풀이
구명보트에는 2명만이 탈 수 있고 최대한 limit 에 가깝게 맞춰서 보내야하기 때문에 우선 사람들의 몸무게를 오름차순으로 정렬한다. 그 다음, 가장 가벼운 사람과 가장 무거운 사람을 가리키는 두 개의 포인터(left, right)를 선언한다.
만약 두 포인터의 몸무게 합이 limit 를 넘어서면 무거운 사람만 먼저 보낸다. 무거운 사람만 보내는 이유는 가벼운 사람은 다음 무거운 사람과 같이 갈 수 있는 확률이 존재하기 때문이다.
만약 두 포인터의 몸무게 합이 limit 이하라면 둘 모두 보내게 된다.