구명보트(39분)

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

구현 아이디어 8분 구현 30분

풀이

실패: 효율성 테스트
1. vector를 정렬한다.
2. begin 하나를 잡고 있고 end에서 하나씩 내려가면서 limit을 넘지 않을 때 end에 있던 원소를 2147000000이라는 수를 대입하여 탔다고 표시한다.

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    // 앞에서 전진
    for(int i = 0; i < people.size(); ++i)
    {   
        if(people[i] == 2147000000) continue;
        // 뒤에서 후진
        for(int j = people.size() - 1; j >= i; --j)
        {
            int sum = people[i] + people[j];
            if(i == j) sum /= 2;
            if(sum > limit)
            {
                continue;
            }
            else
            {
                ++answer;
                people[j] = 2147000000;
                break;
            }
        }
    }
    
    return answer;
}

---

개인적인 감상. 효율성 테스트가 있는 문제는 100이면 100 다 실패하는 듯하다. 효율적인 코드를 짜기 위해서는 어떤 알고리즘을 사용해야 할까... 투포인터를 활용해 다시 풀 예정이다.

---

풀이

내가 딱 이렇게 풀고 싶었는데 이걸 아직 금방 못 풀다니... 다른 사람의 풀이를 참고해서 풀었을 때 굉장히 허망했다. 나는 투포인터에 대한 잘못된 인식이 있는 듯하다. 투포인터 == 이진 탐색이라고 무조건적으로 생각하는 경향이 있는데 투포인터는 말 그대로 두 개의 값을 내 입맛대로 조절해서 풀면 된다!

다음엔 더 빨리 풀테야!

#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 lp = 0, rp = people.size() - 1;
    
    while(lp <= rp)
    {
        if(lp == rp)
        {
            ++answer;
            break;
        }
        if(people[lp] + people[rp] <= limit)
        {
            ++lp;
            --rp;
            ++answer;
        }
        else
        {
            --rp;
            ++answer;
        }
    }
    
    return answer;
}

---

풀이

people을 역순으로 sort하고 무거운 사람 먼저 태운 뒤 가벼운 사람을 고려하는 방법이 있다. 내 풀이는 아니고 프로그래머스 다른 사람의 풀이를 참고했다. 다음에 이 문제를 복기할 때 이렇게 풀고 싶어서 잊지 않기 위해 담아둔다.

새로 안 사실: 내림차순 sort를 하기 위해서는 rbegin()과 rend()를 사용하면 된다.

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.rbegin(), people.rend());
    
    int i = 0;
    int j = people.size() - 1;
    
    for(; i <= j; ++i)
    {
        if(people[i] + people[j] <= limit)
            --j;
        
        answer++;
    }
    
    return answer;
}