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

풀이 문제 : 프로그래머스 구명보트
풀이 언어 : C++
알고리즘 : 그리디
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42885#

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

 

문제요약

구명보트에 최대 2인이 탈수 있고, 무게제한이 있다.
사람들의 몸무게와 무게제한이 주어졌을때, 최소 몇개의 구명보트를 이용해야만 모든 사람들을 구할 수 있는지 알아내야한다. 

 

첫번째 접근방식 (실패)

sort를 해서 무게가 적게 나가는 사람 + 많이 나가는 사람의 총 합 몸무게가 주어진 무게 제한보다 작을때 필요한 구명보트 개수를 늘리고,
모든 반복문을 돌리고 나서 아직 구하지 못한 남은 인원의 개수만큼 구명보트를 더하는 방법을 생각했다.

 

첫번째 접근방식에 대한 코드 (실패)

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

using namespace std;

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

   for (int fi = 0; fi < len;fi++) {
      if (saved[fi] == 1) continue;
      int front = people[fi];
      for (int i = len - 1; i >= 0;i--) {
         if (saved[i] == 1)continue;
         int back = people[i];
         if (front + back > limit) continue;
         else {
            answer += 1;
            saved[fi] = 1;
            saved[i] = 1;
            break;
         }
      }
   }

   for (int yetSaved : saved) {
      if (yetSaved == 0) answer += 1;
   }

   return answer;
}

 

첫번째 방식 결과 (실패)

정확성 테스트 15/15
효율성 테스트 0/5
라는 처참한 결과가 나왔다.

시간복잡도를 계산해보니 O(n^2) 으로 약 25초나 걸린다 ㅋㅋㅋ 이러니까 실패하지;;

최대한 반복문을 줄일 수 있는 방법을 생각해보았다.

 

두번째 접근방식 (정답)

첫번째, 하나의 반복문 안에서 front 와 back 값을 구할 수 있다.

두번째,

반복문을 끝까지 돌아서 확인해볼 필요 없이, front + back이 limit 보다 커지면, back은 일단 구명보트를 혼자 타고 가야한다.
그래서 그 즉시 구명보트 개수를 늘리고 pop_back하면 되겠다고 생각했다.

반대로 limit보다 작은 경우에는 front와 back 모두 pop해야한다.
그런데 vector로는 pop_front가 안된다.
그래서 deque를 사용해야겠다고 생각했다.

세번째,

그런데 이대로만 코드를 짜니까, 입출력 예시 두번째를 통과하지 못했다.

두번째 입출력 예는 다음과 같다

디버깅 결과 deque 에 50만 남았을때 limit보다 작거나 같기 때문에 코드에 따라 pop_back과 pop_front를 해야하는데,
deque에 남은 값이 50 하나뿐이기 때문에 오류가 나는 것이었다.
그래서 이 오류를 고쳐주기 위해 break문을 추가하였다.

 

두번째 접근방식에 대한 코드 (정답코드)

#include <string>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

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

	while (!dpeople.empty()) {
		int front = dpeople.front();
		int back = dpeople.back();

		if (front + back > limit) {
			answer += 1;
			dpeople.pop_back();
		}
		else {
			answer += 1;
			dpeople.pop_back();
			if (dpeople.empty()) break; // 남은 숫자가 50인경우
			dpeople.pop_front();
		}
	}

	return answer;
}

 

결과 (성공)

반복문 하나로 만들어서 효율성 테스트까지 통과했다!

회고

자료구조를 좀더 익혀야겠다..!
그리고 코드를 짜기 전에 시간 복잡도를 계산하고 몇초정도 나오는지 계산하고 들어가자.