[프로그래머스/Greedy] Level 2 구명보트 (JAVA)

문제

---

풀이

1차 시도

1. int 배열을 List로 변환하고 내림차순으로 정렬한다.
2. remains를 처음부터 끝까지 탐색하며 맨 앞 + 맨 뒤 사람을 보트에 태워 보낸다.
   • 가장 무거운 사람을 먼저 태우고
   • 가장 가벼운 사람을 태울 수 있는지 limit를 체크해서
   • 같이 태울 수 있으면 태워 보내고 못 태우면 제일 무거운 사람 한 명만 태워 보낸다.

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        List<Integer> remains = Arrays.stream(people).boxed()
        	.sorted((o1, o2) -> -Integer.compare(o1, o2)).collect(Collectors.toList());
        while (!remains.isEmpty()) {
            answer++;
            int onboardWeight = remains.get(0);
            remains.remove(0);
            if (remains.size() >= 1)
                if (onboardWeight + remains.get(remains.size() - 1) <= limit)
                    remains.remove(remains.size() - 1);
        }
        return answer;
    }
}

이 코드의 문제점은.. 5만명을 태워 보내는 경우 최대 5만번 loop를 돌아야 한다는 거다.
문제를 보자마자 코드부터 짜면 이런 쓰레기 코드가 나온다! 더 빠른 방법에 대해 생각해본 후 코드를 짜기 시작하자!

2차 시도

그래서 중간에 loop를 탈출할 수 있는 조건문을 추가해줬다.

remains 중 가장 무거운 사람의 무게가 limit의 절반 이하면 이제 앞으로 남은 사람들은 다 2명씩 태워서 보내면 되니까 while문을 탈출하도록 한 것이다. 그리고 answer에 남은 사람을 반으로 나눈 값을 더해서 리턴하면 정확성은 100점이다.

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        List<Integer> remains = Arrays.stream(people).boxed()
                .sorted((o1, o2) -> -Integer.compare(o1, o2)).collect(Collectors.toList());
        while (!remains.isEmpty()) {
            answer++;
            int onboardWeight = remains.get(0);
            remains.remove(0);
            if (remains.size() > 0)
                if (onboardWeight + remains.get(remains.size() - 1) <= limit)
                    remains.remove(remains.size() - 1);
            if (remains.size() > 0 && remains.get(0) <= limit / 2) break;
        }        
        return answer + (remains.size() % 2 == 0 ? remains.size() / 2 : remains.size() / 2 + 1);


    }
}

하지만 역시 효율성 검사의 모든 테케에서 시간초과가 떴다. 아무래도 List를 변환하고, element를 remove하는 과정이 오래 걸리는 것 같아서 이 부분을 수정했다.

정답

2차 시도와 로직은 똑같지만

• List로 변환하는 대신 그대로 int배열을 활용한다.
• left와 right 인덱스값을 바꿔가며 배열을 탐색한다.

이렇게 수정했더니 효율성도 100점이 떠서 패스할 수 있었다.

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int left = 0, right = people.length - 1;
        while (left < right) {
            answer++;
            int onboardWeight = people[right--];
            if (left < right && onboardWeight + people[left] <= limit) left++;
            if (left < right && people[right] <= limit / 2) break;
        }
        int remaining = right - left + 1;
        return answer + (remaining % 2 == 0 ? remaining / 2 : remaining / 2 + 1);
    }
}

Lambda와 Collection을 활용하면 코드의 가독성이 좋아지긴 하지만 작동이 빠른건 역시 배열인 것 같다. 항상 자연스럽게 Collection 자료구조, 특히 List를 적극 활용했는데, 알고리즘 문제에서는 효율성을 위해 배열을 주로 사용하도록 노력해야겠다.