[프로그래머스] 구명보트

문제설명

보트는 한번에 두 명씩 탑승 할 수 있으나, 무게 제한을 넘길 수는 없다

최소한으로 보트를 움직이는 수를 구하라

알고리즘

1. 주어진 사람의 무게 벡터를 오름차순으로 정렬한다

2. 제일 가벼운 사람과 그 다음사람 두명이 한 보트에 타지 못한다면, 보트는 인원수 만큼 움직인다

3. 벡터에서 제일 무거운 사람의 무게를 꺼내고 지운다

4. 만약 그 값과 제일 가벼운사람부터 조회하여 한 보트에 탈 수 있는 경우, idx를 증가 시킨다

5. 한 보트에 탈 수 없는 경우 그 사람은 혼자 탄다-> 그 다음으로 무거운 사람을 꺼낸다 

6. 보트에 둘이 탈 수 있던 없던 1씩 증가시킨다 (혼자 타는 경우, 둘이타는 경우 모두 배가 한번 움직임)

코드

#include <vector>
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer=0,idx=0;
    sort(people.begin(),people.end());//오름차순 정렬
    
    if(people[0]+people[1]>limit)//제일 가벼운 사람이 짝을 못짓는 다면, 한번에 한사람 밖에 못탐
            return people.size();
    
    while(people.size()>idx){     
        int back = people.back();
        people.pop_back();
        if(people[idx]+ back<=limit) 
            idx++;        
         answer++;
    }
    return answer;
}

고찰

이번 코드는 구현은 할 수 있었으나 효율성 5개 케이스에서 2개밖에 통과하지 못했다

그 이유는 반복문을 중첩으로 사용하여 구현하였기 때문이다

굳이 전체를 돌면서 할 필요는 없었는데 불필요한 연산을 했기 때문에 데이터가 많아진 경우에 통과하지 못했던 것 같다

패스하지 못한 코드는 다음과 같다 

#include <vector>
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer=0;
    sort(people.begin(),people.end());//오름차순 정렬
    int k=0;
    
    if(people[k]+people[k+1]>limit)//제일 가벼운 사람이 짝을 못짓는 다면, 한번에 한사람 밖에 못탐
            return people.size();
    
    while(1){
        if(k== people.size())//모든 조회 완료시 연산 중지
            break;
        
        if(people[k]==-1){ //조합을 해본 대상이 이미 보트를 타고 나간 경우
            k++;
            continue;          
        }                 
        int min = people[k]; //제일 가벼운 사람 무게 
        
        for(int i= people.size()-1;i>=k; i--){
            if(people[i]==-1)//조합을 해본 대상이 이미 보트를 타고 나간 경우
                continue;
            if(people[i]+min<=limit || k==i){ //짝을 찾지 못했거나 짝을 찾아 나간 경우
                people[i]=people[k]=-1;
                answer++;  
                break;
            }   
        }         
        k++;
    }
    return answer;
}