[알고리즘] 프로그래머스 - 구명보트 c++

문제 링크

프로그래머스 - 구명보트 (Level2)

문제 분석

문제

• 무인도에 갇힌 사람들을 구명보트로 구출하려고 한다.
• 구명 보트에 최대 2명 탈 수 있고, 무게 제한이 있다
• 사람들의 몸무게가 주어졌을 때
• 구명보트를 최소로 사용해서 모든 사람을 무인도에서 구출해라

입력

• 1 ≤ 사람 수 ≤ 50,000
• 40 ≤ 사람의 몸무게 ≤ 240
• 40 ≤ 구명보트 무게제한 ≤ 240
• 사람 최대 몸무게 ≤ 구명 보트 무게제한

구현 방법

시도 1 - 시간초과

• 이중 for문 시간초과
• 결과
  - 정확성 : 81.5 / 81.5
  - 효율성 0.0 / 18.5
  - 합계 : 81.5 / 100.0

  #include <bits/stdc++.h>
  
  using namespace std;
  
  int solution(vector<int> people, int limit) {
      int answer = 0;
      
      sort(people.begin(), people.end());
      vector<bool> chk(people.size(), false);
      for (int i=0; i<people.size(); i++){
          int rest = limit - people[i];
          for (int j=people.size()-1; j > i; j--){
              if (chk[j]) continue;
              if (rest >= people[j]){
                  chk[j] = true; break;
              }
          }
      }
      
      for (int i=0; i<people.size(); i++) {
          if (!chk[i]) answer++; 
      }
      
      return answer;
  }

시도 2 - 풀었다요!!

• 매번 맨 끝에서부터 j 돌 필요 없음
• people[i]는 점차 커지기 때문에 rest는 작아지게 되어있고 j도 작아지게 되어있다. 따라서 그 다음 만족하는 j는 맨 뒤에서 부터가 아니라 그 전에 나왔던 j값부터 시작하면 된다.

  • rest < people[i] 이면 어차피 찾을 수 없음. 이후에도 쭉. 따라서 break;

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int solution(vector<int> people, int limit) {
        int answer = 0;
        
        sort(people.begin(), people.end());
        vector<bool> chk(people.size(), false);
     
        int last = people.size()-1;
        for (int i=0; i<people.size(); i++){
            int rest = limit - people[i];
            if (rest < people[i] || chk[i]) break;
            for (int j=last; j > i; j--){
                if (chk[j]) continue;
                if (rest >= people[j]){
                    last = j;
                    chk[j] = true; break;
                }
            }
        }
        
        for (int i=0; i<people.size(); i++) {
            if (!chk[i]) answer++; 
        }
        
        return answer;
    }

다른 사람의 풀이 : 투포인터

• 투포인터 사용
• 보트에는 최대 2명 밖에 탈 수 없으므로

  #include <bits/stdc++.h>
  
  using namespace std;
  
  int solution(vector<int> people, int limit) {
      int answer = 0;
      sort(people.begin(), people.end(), greater<>());
      int l = 0, r = people.size()-1;
      while (l < r){
          if (people[l]+ people[r] <= limit){
              l++; r--;
          } else l++;
          
          answer++;
      }
      if (l==r) answer++;
      
      return answer;
  }

회고

사실 가장 먼저 든 생각은 이분탐색이었다. N이 5104이었기에 N^2을 하면 시간 초과가 날 것이라고 생각했기 때문이었다. 그렇게 upper bound를 사용해서 구현을 했었다.

그런데 간과한 게 있었다. 이미 사용한 값을 어떻게 처리해줄까? 였다. vector이므로 아예 삭제하려면 하나당 N이라는 시간이 필요하므로 N^2의 시간복잡도가 필요하다. 따라서 값을 지울 수는 없다. 그렇다면 chk 배열을 사용해서 upper bound에서 나온 iterator 값을 뒤로 미뤄주는 처리가 필요했다. 너무 번거로웠다!

다른 방법을 생각해야 했다. 사실 N = 5*10^4이므로 이중 for문으로 어찌 어찌 비비면 시간 초과에 안걸릴 것이라고 생각하고 이것으로 구현했다. 정확성 테스트를 맞추고 시간 복잡도를 낮추기 위한 시도들을 했다. 이중 for문에 제약을 두어 N^2이 풀로 돌지 않게 하였다. 성공했다! 그런데 지금 생각해보면 여기서 조금만 더 나아가면 이게 투포인터였다. 그리고 애초에 투포인터와 이분탐색을 호환 가능하므로 '이분 탐색 하려고 했는데 어렵네..' 라는 생각이 들었으면 투포인터를 먼저 생각해봤어야 했다. 그리고 구명 보트에 탈 수 있는 사람이 최대 2명이라는 것도 힌트였다!

방법을 바꿔 다른 시도를 여러번 한 것을 아주 아주 잘했다. 결국 정답까지 맞췄으니까! 이렇게 방법을 바꾸는 훈련과 자료구조와 알고리즘에 대한 발상 훈련을 더 해야겠다🔥!