구명보트

문제 링크 => 코딩테스트 연습 - 구명보트 | 프로그래머스 (programmers.co.kr)

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

---

이 문제에서 핵심은 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다.

 

그리고 구명 보트는 무게 제한이 있다.

 

예를 들어서 x kg, y kg 의 합 (x + y) kg 에 대하여 (x + y) <= limit 을 만족해야만 2명이 동시에 구명보트를 탈 수 있고 그 외에는 따로따로 타야 한다는 점이 있다.

 

먼저 parameter로 받아온 vector에 대하여 오름차순으로 sorting 을 한다.

 

그 후에 deque에 push를 하고 다음과 같은 과정을 반복한다.

 

1. dq size가 1인 경우 1을 counting 후 빠져나오고 5번으로 이동한다.

2. x = front(), y = back() 에 존재하는 값을 가져온다. (가장 적은 몸무게, 가장 큰 몸무게)

3. (x + y) <= limit 인 경우 =>  2를 counting 하고 front, back에 존재하는 값을 pop

    (x + y) > limit 인 경우 => 1를 counting 하고 back 에 존재하는 값만 pop (가장 작은 값은 pop 하지 않음)

4. 1번으로 돌아간다.

5. 최종 counting 값을 return 한다.

 

풀이 Code

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(vector<int> people, int limit) {
	int answer = 0;
	sort(people.begin(), people.end());

	deque<int> dq;

	for (int i = 0; i < people.size(); i++) {
		dq.push_back(people[i]);
	}

	int cnt = 0;
	while (!dq.empty()) {
		if (dq.size() == 1) {
			cnt++;
			break;
		}

		int x = dq.front();
		int y = dq.back(); 

		if (x + y <= limit) {
			dq.pop_front(); 
			dq.pop_back();
		}
		else {
			dq.pop_back();
		}
		cnt++;
	}

	return cnt;
}