🖊️ 문제

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

---

🖊️ 풀이

일단 주어진 상황에서 조건이

1. 최대 2명만 탑승 가능
2. 무게 제한 이하로만 탑승 가능

이니까,
기본적으로 가장 가벼운 사람 과 가장 무거운 사람이 같이 탑승하면 되겠다.

그래서 일단 people 벡터를 오름차순으로 정렬해준 뒤에,
순차적으로 돌면서 가장 가벼운 애(front), 가장 무거운 애(back)를 짝지어준다.
그래서 만약 무게 제한 보다 가벼우면 한 보트에 태우고 (가벼운 애도 태움),
무게 제한보다 무거우면 무거운 애를 일단 보트에 혼자 태우고 (가장 가벼운 애랑도 못타니까 얘는 무조건 혼자 타야됨), 가벼운 애는 그 다음 무거운 애랑 짝지어질 수도 있으니까 냅둔다.

이렇게 전체적인 알고리즘을 짜고,
전체 벡터에서 삭제시켜주는 방식으로 구현했더니
바로 시간초과 ㅋㅋ

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    while(!people.empty()) {
        if (people.size() == 1) {
            answer++;
            people.pop_back();
            break;
        }
        else if (people.front() + people.back() <= limit) {
            people.erase(people.begin());
        }
        answer++;
        people.pop_back();
    }
    
  
    return answer;
}

소녀는 울지않긔

왜그럴까? 고민해봤는데,
벡터는 메모리 상에서 연속된 공간을 갖기 때문에, 특정 위치에 존재한 원소를 삭제하면 뒤에 있는 애들을 앞으로 밀어줘야 한다. 그래서 특정 위치의 원소를 삭제하는 erase 는 O(n)의 시간복잡도를 갖는다 !!

어차피 무조건 삭제될 원소인 가장 무거운 애는 무조건 맨 뒤 원소라 pop_back쓰면 O(1)로 때려버릴 수 있지만, 맨 앞의 원소를 삭제하는 erase연산을 처리해주지 않으면 이 시간초과가 개선되지 않을 것 같았다.

벡터에서 특정 위치의 원소에 접근하는 것은 O(1)이고,
딱히 삭제할 필요 없이, 현재 탑승한 애들의 개수만 세어줘도 되니까,
이를 활용해서 코드를 고쳐보자.

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    vector<int>::iterator light = people.begin();
    vector<int>::iterator heavy = people.end() - 1;
    
    while(light <= heavy) {
        if (*light + *heavy <= limit) {
            light++;
        }
        answer++;
        heavy--;
    }
  
    return answer;
}

굿 ~