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

(7/2 - X)

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

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

 

 

구현

총 두 가지를 생각해 내야 하는데,

1. 어떻게 하면 최대한 적은 보트를 쓰면서 사람을 태울 수 있는가 -> 최소 몸무게와 최대 몸무게를 태운다. (Greedy)

2. 어떻게 하면 제한 시간을 초과하지 않게 적절한 자료구조 선택/코드 구상을 할 것인가. (코딩 실력..)

 

 

나는 2에서 막혔다.

처음에 짰던 코드는 sort를 한 후 최소 몸무게+최대 몸무게를 비교한 후 limit을 넘으면 그 다음으로 최대 몸무게를 다시 최소 몸무게랑 더해서 인덱스을 감소시키는 형태로 풀었다.

 

구글링을 한 후 "최소 몸무게와도 못 타면 최대 몸무게는 혼자 탈 수밖에 없다"라는 사실을 알았다.

앞뒤 pop이 가능한 deque 자료구조에 넣고, 최소와 최대를 더해서 limit을 넘는다면 바로 pop_back()을 하고 answer를 증가시키고, limit을 넘지 않는다면 pop_back, pop_front를 하는 방식으로 구현했다.

 

 

실수

시퀀셜한 자료구조는 erase나 pop을 하면 컨테이너의 부분 메모리가 아닌 전체 메모리 복사가 이루어지기 때문에 남발하게 되면 시간 초과가 일어날 수 있다. 메모리의 복사를 최소로 줄여야 한다.

 

 

코드

// 프로그래머스 고득점 kit - greedy - 구명보트
#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
	deque<int> d;
	for (const auto& i : people) {
		d.push_back(i);
	}
    sort(d.begin(), d.end());
	while (!d.empty()) {
		if (*(d.begin()) + *(d.end() - 1) <= limit) {
			answer++;
			d.pop_back();
			if (d.empty()) 
				break;
			d.pop_front();
		}
		else {
			answer++;
			d.pop_back();
		}

    }
    return answer;
}
int main() {
    vector<int> v{ 70,50, 80,50 };
    solution(v, 100);
}