(강추)프로그래머스. 구명보트(c++) / Greedy+Two pointer

그리디+투포인터를 사용한 문제였다.

문제를 처음봤을 때 정확히 풀이가 떠오르지는 않았지만, 어차피 2명이 최대이고 limit이 주어져서 i, j 인덱스로 해결할 수 있을 것이라 생각했다.

 

[메인 로직]

중요한 점은, i, j모두 전역변수로 선언해주어야 한다는 것!!!!

people배열을 정렬하고 j는 맨뒤부터, i는 맨 앞부터 탐색하도록 했다.

그리고 i, j의 합이 limit이하면 두명이서 보트를 탈 수 있기 때문에 i++, answer++했고

limit을 초과하면 그냥 answer++하고 넘어간다.

이후, i==j인 경우는 answer++을 한 번 더 해준다.

 

첫 번째 풀이

for문을 사용해서 푸는 방법

 

// 구명보트
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    int i=0, j=0;
    
    sort(people.begin(), people.end());
    
    // int j로 선언하면 노노.... 뒤에서 i==j인 경우를 따져야하기 때문에 i, j는 전역변수로 선언해야 함!
    for(j=people.size()-1; j>i; j--){
        if(people[j]+people[i]<=limit){
            i++;
            answer++;
        }else{
            answer++;
        }
    }
    
    // ex) [30, 40, 50], limit = 100의 경우 i==j에서 멈춘다. 그래서 i==j일 경우 answer++
    if(i==j){
        answer++;
    }
    
    return answer;
}

 

두 번째 풀이

while문을 사용해서 푸는 방법

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    int i=0, j=people.size()-1;
    
    sort(people.begin(), people.end());
    
    while(i<j){
        if(people[i]+people[j]<=limit){
            i++;
            answer++;
        }else{
            answer++;
        }
        j--;
    }
    
    if(i==j){
        answer++;
    }
    
    
    return answer;
}