(7/2 - X)
https://programmers.co.kr/learn/courses/30/lessons/42885
코딩테스트 연습 - 구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5
programmers.co.kr
구현
총 두 가지를 생각해 내야 하는데,
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);
}
'알고리즘 > Programmers' 카테고리의 다른 글
| [프로그래머스/C++] 베스트 앨범 (0) | 2022.07.15 |
|---|---|
| [프로그래머스/C++] 등굣길 (0) | 2022.07.14 |
| [프로그래머스/C++] 디스크 컨트롤러 (0) | 2022.06.28 |
| [프로그래머스/C++] 단어 변환 (0) | 2022.06.27 |
| [프로그래머스/C++] 다리를 지나는 트럭 (0) | 2022.06.27 |
