[프로그래머스][JAVA][Lv. 2] 구명보트

문제 설명

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

---

제한 사항

---

입출력 예

---

풀이

import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        ArrayList<Integer> peopleList = new ArrayList<>();
        
        for (int i : people) peopleList.add(i);
        Collections.sort(peopleList, (i, j) -> j - i);
        
        for (int i = 0; i < peopleList.size(); i++) {
            if (peopleList.get(i) == limit + 1) continue;
            int tempLimit = limit - peopleList.get(i);
            
            peopleList.set(i, limit + 1);
            for (int j = i + 1; j < peopleList.size(); j++) {
                if (peopleList.get(j) <= tempLimit) {
                    peopleList.set(j, limit + 1);
                    break;
                }
            }
            answer++;
        }
        
        return answer;
    }
}

 ㄴ 통과는 했으나 효율성 테스트에서 모두 통과하지 못한 코드

 

import java.util.Arrays;

class Solution {    
    public int solution(int[] people, int limit) {
        int answer = 0;
        int pre = 0;
        int post = people.length - 1;
        
        Arrays.sort(people);
        while(post >= pre) {
            if (people[pre] + people[post] <= limit) {
                pre++;
                post--;
            }
            else post--;
            answer++;
        }
        
        return answer;
    }
}

 ㄴ 모든 케이스를 통과한 코드

---

후기

처음에 단순하게 머릿속에 떠오른 대로 내림차순으로 정렬 후 사람 리스트를 이용해서 전체를 한 번 순회하면서 그다음 수부터 또 전체를 순회하는 식으로 풀었는데 모든 테스트 케이스는 통과하나 효율성 테스트에서 모두 실패했다. 이유는 시간 초과인데 아무래도 이중 for문을 반복하다 보니 그랬던 것 같다. 그 후로 정렬이 문제인지 순회하는 방법이 문제인지 몇 시간 동안 생각해 보고 코드를 수정했는데 아무리 생각해 봐도 Arrays.sort()보다 내가 더 빠르게 정렬을 할 방법을 찾지 못했다. 그러다가 오늘 갑자기 머릿속에 떠오른 방법으로 제출해 봤는데 한방에 통과했다. 통과한 풀이는 양쪽 끝에 pre, post 변수로 인덱스를 저장하고 가장 큰 몸무게와 가장 작은 몸무게를 더한 값이 limit보다 작거나 같으면 pre 증가, post 감소를 하고, 아닐 경우에는 몸무게가 많이 나가는 쪽인 post만 감소시킨다. 한 번에 두 명만 탈 수 있으니 최대 pre, post 변형으로 두 명만 처리할 수 있는 것이다.

그리고 문제에서 "구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다." 라고 하는데 최댓값보다 큰 게 아니라 같거나 큰 것이었다. 몸무게가 limit보다 무조건 작은 게 아니라 같은 경우도 있는 것이다. 물론 그 위에 몸무게와 limit 범위가 나와 있긴 하지만 이 문장 때문에 푸는게 헷갈렸다.