• 문제

C++ Vector 최대값, 최소값, 인덱스 구하기

피드백

한 번에 최대 2명씩 밖에 탈 수 없고 → 아….

sort(people.rbegin(), people.rend())

사용하면 내림차순 정렬도 가능했음..

1. 틀린 코드 (보트에 여러명 태우려고 함)

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

using namespace std;

int solution(vector<int> people, int limit) {
    int boat = 0;  // 초기화 안 되어 있던 변수 초기화
    int answer = 0;
    int len = people.size();
    int check = limit;

    // 가벼운 순서로 정렬
    sort(people.begin(), people.end());

    // people이 빌 때까지 반복
    while (!people.empty()) {  // size() 체크보다 empty()가 더 안전함
        // 탑승 가능한 사람 중 가장 무거운 사람부터 태우기
        for (int i = people.size() - 1; i >= 0; i--) {
            if (people[i] <= check) {
                boat += people[i];
                people.erase(people.begin() + i);
                check = limit - boat;
            }
        }

        // 남은 무게, 남은 사람 수 갱신
        check = limit - boat;
        len = people.size();

        // 더 탈 수 있는 사람이 없어지면 보트 출발
        if (!people.empty() && check < people[0]) {  
            boat = 0;
            answer++;
            check = limit;
        }

        // 남은 사람이 없으면 루프 종료
        if (people.empty()) {
            answer++;  // 마지막 보트 출발
            break;
        }
    }

    return answer;
}

1. 맞춘 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int small = 0, big = people.size() - 1;
    
    // 무게순 정렬
    sort(people.begin(), people.end());

    while (small <= big) {
        // 가장 무거운 사람 태우기
        if (people[big] + people[small] <= limit) {
            small++;  // 가장 가벼운 사람도 같이 태울 수 있음
        }
        // 무거운 사람은 항상 태우기 때문에 right 감소
        big--;
        answer++;  // 보트 사용
    }
    
    return answer;
}