코딩테스트 및 개인공부/문제풀이

[프로그래머스 - level2] [탐욕법] 구명보트

JJPearl 2021. 11. 30. 03:11
반응형

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항
  • 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
  • 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

입출력 예
people limit return
[70, 50, 80, 50] 100 3
[70, 80, 50] 100 3

 

풀이 과정

더보기

<첫번째 풀이>

한번에 2명 탈수 있고, 무게제한(limit) 있는 구명보트를 최대한 적은 횟수로 사용

1. 몸무게 적은 순으로 people 정렬

2. 반복문 내부에서 people의 i,i+1 인덱스 원소끼리 더해서 limit을 안 넘는다면 구명보트 1번에 2명 -> i+=2

   넘는다면 구명보트 1번에 1명  -> i++

 

-> 적은 순으로 정렬해서 냅다 옆 인덱스랑 더해버리면

40,50,150,160 limit = 200 => 2 일 때 반례가 생긴다.

높은 순으로 정렬 후 앞쪽의 큰 값과 뒤쪽의 작은 값, 양 끝을 더해서 탐색해야 한다.

 

1. 몸무게 높은 순으로 people 정렬

2. 이중 반복문 i,j 사용. i는 앞쪽 높은 몸무게의 인덱스, j는 뒤쪽 적은 몸무게 탐색용. people의 i,j인덱스 원소끼리 더해서 limit을 안넘는다면 둘다 삭제후 answer++

넘는다면 i 인덱스 원소만 삭제후 answer++

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0; // 구명보트 횟수
    sort(people.begin(),people.end(),greater<int>());
    for(auto i = people.begin(); i != people.end();) {
        if(people.size() >= 2) {
        for(auto j = people.end()-1; j != people.begin(); --j) {
           if(*i + *j <= limit) {
               people.erase(j); // index out of range 나지 않도록 뒤의 원소부터 erase
               people.erase(i);
               break;
           }
            else {
                people.erase(i);
                break;
            }
        }
        i = people.begin();
        ++answer;   
    }
    else {
        ++answer;
        break;
    }
    }
    return answer;
}

-> 정확성은 만점인데 효율성이 전부 실패로 뜬다.

아마 정렬 후 처음 원소와 끝 원소를 하나씩 전부 비교하는 방식이라 오래걸리는 것 같다??

->

혹시나 vector의 erase() 연산이 오래걸리나 싶어 검색해 봤는데 erase연산의 시간 복잡도가 O(n)이라고 한다.

- vector::erase(vector::begin()) 연산은 container의 size에 비례하는 시간이 걸립니다.

- STL은 시간복잡도의 한계를 넘어설 수 있는 마법이 아니라, 익히 알려진 자료구조를 '잘' 구현한 라이브러리에 불과합니다.
랜덤 액세스를 항상 O(1)에 할 수 있다는 건 벡터는 평범한 동적 배열의 형태라는 뜻이고, 배열의 임의의 원소를 제거하고도 인덱스를 그대로 유지하려면 뒤에 있는 원소들을 전부 앞으로 당겨오는 수밖에 없습니다.
벡터 뿐만 아니라 STL의 어떤 기능을 쓰더라도, 각각 어떤 자료구조를 사용하고 그에 대한 연산들이 어떤 시간복잡도를 가지는지 숙지하고 사용하는 것이 좋습니다.

- vector의 insert와 erase 함수 모두 O(n) 으로 느린편입니다.

내 첫번째 풀이는 이중 포문에 erase()까지 쓰니 효율성이 제대로 나올 수가 없다.

erase()를 쓰지 않고 구현해보자.

로직은 그대로 하되 erase를 대체해서 구현했다.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
	int answer = 0; // 구명보트 횟수
	int indexJ = 1; // 정렬된 벡터의 끝에서 삭제되었다고 칠 수 있도록 end iter에서 indexJ만큼 빼준다.
	sort(people.begin(), people.end(), greater<int>());
	for (auto i = people.begin(); i != people.end();) {
			for (auto j = people.end() - indexJ; j != i; --j) {
					if (*i + *j <= limit) {	
						++indexJ;
						break;
					}
					else {
						break;
					}
				
			}
			++answer;
			if (i != people.end() - indexJ) {
				++i;
			}
			else
				break;
	}
	return answer;
}

->

질문하기에서 본건데 아래 방법처럼 하면 효율성을 더 높여서 짤 수도 있을 것 같다.

효율성을 더 좋게하려면 양 끝에 있는 사람끼리 더해서 같이 보낼 수 있으면 보내고, 아니면 앞에 사람만 보내는걸 반복하다가
맨앞의 사람이 보트 제한 무게의 절반 이하가 되면 무조건 맨 뒤의 사람과 같이 보낼 수 있으므로
남은 사람들은 남은 사람들 수의 절반의 보트 횟수만 있으면 된다!

 

필요 지식

- 이터레이터 무효화 주의

컨테이너에 원소를 추가하거나 제거하게 되면 기존에 사용하였던 모든 반복자들을 사용할 수 없게됩니다.
다시 말해 위 경우 vec.erase(itr) 을 수행하게 되면 더이상 itr 은 유효한 반복자가 아니게 되는 것이지요. 또한 end_itr 역시 무효화 됩니다.
따라서 itr != end_itr 이 영원히 성립되며 무한 루프에 빠지게되어 위와 같은 오류가 발생합니다.

https://modoocode.com/223

 

씹어먹는 C++ - <10 - 1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)>

 

modoocode.com

- 벡터는 삽입,삭제 할 때마다 동적으로 size가 늘어나거나 줄어들기 때문에 삽입,삭제 연산 직후 기존의 인덱스, 이터레이터가 바뀐다.

 

 

반응형