Programmers: 구명보트

문제

• https://programmers.co.kr/learn/courses/30/lessons/42885
• 분류: 그리디 / 이분탐색[약간?]

문제 설명

• 한 보트에는 최대 2명만 탑승 가능
• 두명이 타도, 두명의 몸무게 합이 보트의 최대 무게보다 작거나 같아야됨
  • first_people + second_people <= boat_limit
• 보트를 최소한으로 움직이는 횟수를 구하기

아주 간단한 접근[=틀림]

• 그리디!
• 정렬하고 앞에 두명씩 더해서 보트 보낼 수 있으면 보내고 아니면 한명만 보내기
• 당연히 틀림
  • [20, 20, 20, 80, 80, 80] 케이스의 경우에서 방금 알고리즘은
  • [20, 20], [20, 80], [80], [80] 총 4번 움직이지만
  • 실제 답은 3번 움직여야 됨

따라서[효율성 X]

• 일단 정렬까지는 동일
• 앞에 원소 하나 가져온 다음에, 보트 최대 무게를 견딜 수 있는 사람을 찾음
  • 즉, 앞의 원소가 20이면, 태울 수 있는 다른 사람의 무게는 80이기 때문에 80부터 0까지 쭉 찾아본다
• 보트 최대 무게를 견딜 수 있으면 보트 운영횟수 ++
• 최대 무게를 견디지 못해서 한명만 타도 운영횟수++
• 이걸 사용하니까 정확성은 100%는 맞았지만 효율성 '0점'

따라서[+효율성]

• 질문글을 검색하다가 앞-뒤 동시 체크 관련된 질문을 보았다. 머리 탁!
• 효율성 없는 알고리즘은 보트를 채울 수 있는 사람을 배열 반복을 통해 검색하지만 이건 아니었다.

알고리즘

• 일단 정렬
• 앞을 나타내는 i 변수와 뒤를 나타내는 i_end를 선언
• i <= i_end 조건으로 while문 실행
  • people[i_end] + people[i] <= limit이 참인 경우
    • 둘다 탄거니까 i_end는 감소, i는 증가 시킨다
    • 보트 운영 횟수 증가
  • 아닌 경우
    • people[i_end]만 탈 수 있다.
    • 그래서 i_end는 감소, i는 그대로 놔둔다
    • 보트 운영횟수 증가
• 계속 반복한다

효율성X 코드

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

using namespace std;

#define BOAT_LIMIT 2
#define NO_FALSE -10

unordered_set<int> check;

int find_other_people(vector<int>& people, int boat, int cur_i, int limit) {
    for (int i = people.size()-1; i >= cur_i; i--) {
        if (check.find(i) != check.end()) {
            continue; // skip
        }

        if (boat + people[i] <= limit) {
            check.insert(i);
            return people[i];
        }
    }


    return NO_FALSE;
}

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());

    int boat = 0;
    int i = 0;
    while (i < people.size()) {
        if (check.find(i) != check.end()) {
            i++; continue;
        }

        if (boat == 0) {
            boat += people[i]; check.insert(i);
            // cout << "Cur Boat: " << boat << endl;
            find_other_people(people, boat, i, limit);

            boat = 0;
            answer++;
            // cout << "Ans: " << answer << endl;
        }
        i++;
    }
    return answer;
}

최종 코드

#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 boat = 0;
    int i = 0;
    int i_end = people.size() - 1;
    while (i <= i_end) {
        if (people[i_end] + people[i] <= limit) {
            i++;
            i_end--;
            answer++;
        } else {
            i_end--;
            answer++;
        }
    }
    return answer;
}