[프로그래머스/Java] 구명보트(Greedy 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 Greedy 문제 중 '구명보트' 문제를 자바로 풀어보았다.

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

프로그래머스

 

 

 

 우선 처음에 접근할 때는 아래 코드와 같이 리스트로 풀어보았다. 답은 전부 맞았으나, 효율성 측면에서 틀린 답이라고 나왔다.  List에 쓰고 지우는 과정이 시간효율성이 떨어져서 생긴 문제라고 생각해서 List로 변환하는 과정을 제거하고 Array로 바로 처리하는 방식으로 변경했다.

import java.util.*;

class Solution {
    public int solution(int[] p, int limit) {
        int answer = 0;
        Arrays.sort(p);
        List<Integer> people = new ArrayList<>();
        for (int n : p) people.add(n);
        
         while (!people.isEmpty()) {
             answer++;
             int cur = limit - people.get(0);
             people.remove(0);
            
             int j = people.size()-1;
             while (j >= 0 && people.get(j) > cur) j--;
             if (j >= 0) people.remove(j);
             else break;
         }
        
        return answer + people.size();
    }
}

 

 

 

 변경한 코드는 아래와 같다. 우선 주어진 array를 오름차순 정렬해 준다. 그리고 가장 작은 값부터 하나씩 접근해서 구명보트에 태운다. 이때, 태운 사람을 (limit+1)으로 표현한다. (문제 조건으로 사람들의 무게는 limt보다 작거나 같아서, 그 사람이 구명보트에 못 타는 경우는 없다고 했으므로, 이를 이용하여 표기해 주는 것이다.) 그러고 나서 큰 값부터 순회하면서, 현재 사람과 함께 탈 수 있는 사람 중 가장 무거운 사람을 찾는다. 여기서 가장 무거운 사람을 찾기 때문에 greedy 알고리즘이라고 할 수 있다. 이때, (j >= 0)이 아니면 break 하는 이유는, j >= 0이 아니라는 것은 남은 값들 중 현재 사람과 함께 구명보트에 탈 수 있는 몸무게인 사람이 없다는 뜻이다. 그런데 현재 사람이 남아있는 사람들 중에 몸무게가 가장 가볍다. (가벼운 사람부터 순회하기 때문이다.) 그러므로, 현재 사람과 함께 탈 수 있는 사람이 없다는 건, 앞으로 2명이 구명보트에 탈 수 있는 경우는 없다는 것이다. 그래서 이 순회를 멈춰주고, p 배열에 남은 사람들의 수를 세서 answer에 더해준다. 

 사실 알고리즘 구조 같은 경우는 리스트를 사용한 위 코드에서 더 잘 드러난다. 위 코드를 array에 맞게 변경한 것이 지금 코드라고 보면 된다. 

import java.util.*;

class Solution {
    public int solution(int[] p, int limit) {
        int answer = 0;
        Arrays.sort(p);
        
        int j = p.length - 1;
        int i;
        for (i = 0; i < p.length; i++) {
            if (p[i] > limit) continue;
            answer++;
            int cur = limit - p[i];
            p[i] = limit + 1;
            
            while (j >= 0 && p[j] > cur) j--;
            if (j >= 0) p[j] = limit + 1;
            else break;
        }
        
        for (; i < p.length; i++) {
            if (p[i] <= limit) answer++;
        }
        
        return answer;
    }
}