프로그래머스 - 구명보트 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/42885#qna

프로그래머스

 

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    int l=0,r=people.size()-1;
    sort(people.begin(),people.end());
    
    while(l<=r)
    {
        if(people[l]+people[r]<=limit)
        {
            l++;
            r--;
            answer++;
        }
        else
        {
            r--;
            answer++;
        }
    }
    
    return answer;
}

 

최대 2인이 탈 수있고 무게제한이 있는 보트로 사람들을 구출해야한다. 이 때, 최소한의 보트로 구하려면 몇개의 보트가 필요한가가 문제이다. 

 

최대한 많은 인원을 2인으로 태우면 된다. 

 

처음엔 이 생각을 가지고 그대로 코드로 옮겼다. 

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(),people.end());
    
    int maxId=-1;
    // limit - 최솟값 보다 큰 사람은 무조건 혼자 타야함
    for(int i=0;i<people.size();i++)
    {
        if(limit-people[i]<people[0])
        {
            maxId=i;
            break;
        }
    }
    if(maxId==-1)
        maxId=people.size();
    int i=0;
    int cnt=people.size()-maxId;
    answer=cnt;
    while(cnt!=people.size())
    {
        for(i=0;i<maxId;i++)
        {
            if(flag[i]==false)
                break;
        }
        bool ch=false;
        for(int j=maxId-1;j>=i+1;j--)
        {
            if(flag[j]==false)
            {
                if(people[i]+people[j]<=limit)
                {
                    flag[j]=true;
                    flag[i]=true;
                    ch=true;
                    cnt+=2;
                    break;
                }
            }
        }
        if(ch==false)
        {
            flag[i]=true;
            cnt++;
        }
        answer++;
    }
    
    return answer;
}

먼저 혼자 탈 수밖에 없는 사람을 계산한다. 

무게제한 - 가장 작은 사람의 무게 < 현재 이 사람의 무게 면 둘이서 탈 수 없는 사람이다. 

오름차순 정렬을 했기 때문에 이 조건에 걸리는 인덱스를 파악하고

 

그 다음, 구한사람은 flag 에 표시했다.

while문을 통해 구하지 않은 사람 중 가장 작은 인덱스를 설정하고 제일 무거운 사람부터 같이 탈 수 있는지를 체크한다.

그래서 둘이 탈 수 있다면 둘을 구하고 아니면 현재 사람만 구한다. 

 

이런식으로 계산하니 효율성에서 5개중 3개만 통과를 하였다. 

 

질문하기에서 살펴보니 투포인터 기법으로 아주 간단하게 해결을 하였다. 

접근은 동일한데, 번거롭게 구하지않은 사람을 찾으려고 i를 찾는 for문과 거꾸로 j를 찾기위해 for문을 계속 돌렸기 때문에 효율성에서 실패가 떴던것 같다. 

 

위에 있는 코드처럼 투포인터로 정렬 후, 바로 l과 r을 통해서 조건비교후 인덱스만 바꾼다. 

굳이 i와 j를 찾으려고 for문을 돌릴 필요가 없었던 것 같다. 

 

 

 

이 문제를 해결하는 과정에서 알고리즘에 대한 필요성을 느끼게 되었다. 

문제를 보고 해결할 때, A 방식으로 접근하면 된다는 생각을 가지고 내가 생각하는 방식을 그대로 코드로 옮길때

다소 복잡한 코드가 되었는데, 

이러한 구조를 코드에서는 투포인터라는 방식으로 아주 쉽게 나타낼 수 있다는 것을 알았다면 훨씬 빠르게 그리고 효율적인 코드를 간결하게 나타낼 수 있었을 것이다. 

따라서 코딩을 많이 해보는 것도 중요하지만 알고리즘을 공부하며 이러한 기법들을 익히는 것도 중요하다는 것을 배웠다.