[PS] 구명보트

문제

프로그래머스

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값 구하기

 

풀이

무게제한을 맞춰야 하므로 가장 무거운 사람부터 넣어보는 것을 생각할 수 있다.

이때, 이 사람과 누가 함께 같이 타느냐가 문제이다.

 

(가장 무거운 사람 + 가장 가벼운 사람)

조합으로 무게 계산을 해보았을 때를 생각해보자.

(1) 무게 초과 -> 가장 무거운 사람은 혼자 타야만 함
(2) 무게 적정 -> 가장 무거운 사람은 가장 가벼운 사람과 같이 탈 수 있음

 

따라서 가장 무거운 사람부터 시작해서 가장 가벼운 사람과 비교한 뒤,

보트의 수를 늘릴지 여부를 체크한다.

 

코드

1. 시간 초과 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(),people.end(), greater<int>());
    
    int weight = 0; int answer = 0; vector<bool> isEscaped(people.size(), false);
    
    for (int i = 0; i < people.size(); i++){
        if (isEscaped[i] == true) continue;
        weight = people[i];
        isEscaped[i] = true;
        
        for (int j = 1; i + j < people.size(); j++){
            if (weight + people[i+j] <= limit && !isEscaped[i+j]){
                isEscaped[i+j] = true;
                break;
            }
        }
        
        answer++;
    }
    
    return answer;
}

 

O(n²) 시간복잡도를 가져서 시간 초과가 났다..

가장 큰 수와 그 다음으로 무게 조건을 만족하는 작은 수 중 가장 큰 수를 넣으려고 하니,

총 연산이 대략 n x n번 발생한다.

 

시간 복잡도를 줄이기 위해 투포인터 방법으로 풀이해보았다.

 

2. 투포인터

투포인터 배열이란, 일차원 배열에서 두 개의 포인터를 서로 다른 방향으로 이동시키면서

원하는 조건을 만족하는 부분 배열이나 원소들을 찾는 방법을 말한다.

 

나는 내림차순으로 정렬하여 가장 무거운 사람부터 무게를 확인하고,

가장 가벼운 사람을 같이 선택할지 여부를 결정했다.

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

using namespace std;

int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end(), greater<int>()); // 내림차순
    int highIdx = 0; // 가장 무거운 사람의 인덱스
    int lowIdx = people.size() - 1; // 가장 가벼운 사람의 인덱스
    int answer = 0; // 보트의 개수
    
    while (highIdx <= lowIdx){
        if (highIdx < lowIdx && people[highIdx] + people[lowIdx] <= limit){
            // 가장 가벼운 사람 포함 가능, 따라서 인덱스 감소
            lowIdx--;
        }
        
        // 가장 무거운 사람은 항상 포함된다
        highIdx++;
        answer++;
    }
    
    return answer;
}

 

회고

시간 초과가 나는 문제를 만나면 당황스럽다.

시간 복잡도까지 생각하지 않고 문제를 풀었기 때문인데..

 

어떤 문제든 가장 최적의 방법을 제공하는 알고리즘이 있듯,

여러분 문제를 풀어보면서 어떤 문제에 어떤 방법이 최적인지 판단하는 것이 알고리즘을 공부하면서 가장 핵심인 것 같다.

시간 초과야 고마워.....!!!!!!!