프로그래머스 - 구명보트

programmers.co.kr/learn/courses/30/lessons/42885#

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

 

처음에 풀때는 단순히 오름차순 정렬해서 앞뒤로 두개씩 비교해서 limit 를 넘는지 아닌지로 판별하려 했으나

입력 : [10, 20, 30, 40, 50, 60, 70, 80, 90], 100 에서 

결과 : 5 가 나와야 했으나,

앞뒤로 두개씩 비교하다 보니, 7이 나왔다.

그래서 이런 방식 대신 투포인터 기법을 사용해야한다.

(입력의 최대 크기가 5만 이므로 O(N^2) 이상의 알고리즘 작성시 시간 초과)

맨 앞부터 탐색하는 변수 s 와 맨 뒤 부터 탐색하는 변수 e 를 써서

limit 를 넘는 경우와 아닌 경우에 따라서 나눠서 처리를 해준다

limit 이하이면, 구명 보트에 두 사람이 탈 수 있는 것이므로 s, e 둘다 변화를 주고,

그렇지 않으면 구명 보트에 한명만 탈 수 있는 것이며, 전체를 다 확인해보기 위해, --e 를 해서 끝 탐색만 앞으로 당긴다.

 

- c++

 

#include <bits/stdc++.h>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0, size = people.size();
    
    sort(people.begin(), people.end());
    
    int s = 0, e = size - 1;
    while(s <= e) {
        if (people[s] + people[e] <= limit) {
            ++s;
            --e;
        } else {
            --e;
        }
        ++answer;
    }
    
    return answer;
}