[Java] 프로그래머스(level-2) - 구명보트

입출력 예시

Input-1
people = [70, 50, 80, 50]
limit = 100
Output-1
3

Input-2
people = [70, 80, 50]
limit = 100
Output-2
3

문제 풀이

---

먼저, 보트에는 단 2명만 탈 수 있다는 점을 유의해야 한다.
문제를 풀기 위한 아이디어 자체는 간단하다.

초안 아이디어

• 무게제한/2 을 넘는 사람이면, 한 보트에 혼자 태워 보낸다.
• 무게제한/2 을 넘지 않는 사람이면, 이미 태워 보낸 보트에 탈 수 있는지 확인하고 탈 수 있다면 타고, 탈 수 없다면 새 보트에 탄다.

위 아이디어를 적용해보자.

people=[70,50,80,50], limit=100 일 떄,
80 -> 80>50(limit/2) -> 새 보트=[80]
70 -> 70>50(limit/2) -> 새 보트=[80,70]
50 -> 50==50(limit/2) -> 새 보트=[80,70,50]
50 -> 50==50(limit/2) -> 기존 보트=[80,70,50+50]

people=[40,50,160,150], limit=200 일 떄,
160 -> 160>100 -> 새 보트=[160]
150 -> 150>100 -> 새 보트=[160,150]
50 -> 50<100 -> 기존 보트=[160,150+50]
40 -> 40<100 -> 기존 보트=[160+40,150+50]

테스트케이스 실패 및 시간초과 발생

people = {70,50,80,50}, limit = 100
people = {70,80,50}, limit = 100
people = {40, 50, 150, 160}, limit = 200
people = {100,500,500,900,950}limit = 1000
people = {40,40,40}, limit = 120
people = {40,40,40,40,50}, limit = 200
people = {40, 55, 55, 60, 60, 60, 70, 80}, limit = 100
people = {40}, limit = 100
people = {60,60,51,51,100}, limit = 100

하지만, 위와 같은 다양한 반례들을 테스트하면서, 조건식의 검증이 불가함을 알게 되었다. 살펴보니, 무거운 사람부터 가벼운 사람순으로 순회하며 무게제한/2 을 넘긴 사람이면 새 보트 배열에 추가되는데 여기서 이중 for문을 통해 새 보트 배열의 원소를 추가로 탐색하게 되면서 조건식을 검증할 수 없었다.
거기다 코드의 가독성도 너무 떨어진 상태이기에 처음부터 다시 아이디어를 생각한 후 코드를 작성하기로 결심하였다.

최종 아이디어

처음부터 다시 아이디어를 차분히 생각해보았다.

• 먼저 무거운 사람부터 보트에 태워 보내기 위해 people배열을 내림차순으로 정렬한다.
• 제일 무거운 사람과 제일 가벼운 사람의 합이 보트의 무게 제한을 넘는지 확인한다.
  • 무게 제한을 넘는다면 제일 무거운 사람만 보트에 태운다.
  • 무게 제한을 넘지 않는다면 같이 탈 수 있으므로 같이 보트에 태운다.

위 아이디어를 어떻게 구현할지 예를 들어보자.

내림차순 정렬하여 people=[80,70,50,50], limit=100 일 때,
1. 80 -> 80+50=130 > limit -> 80만 보트 탑승
2. 70 -> 70+50=120 > limit -> 70만 보트 탑승
3. 50 -> 50+50=100 == limit -> 50과 50 함께 보트 탑승
4. 50 -> 3번에서 이미 탑승함

그럼 코드로 한 번 작성해보자.

int answer = 0;
Integer[] tmp = Arrays.stream(people).boxed().toArray(Integer[]::new); 
Arrays.sort(tmp, Collections.reverseOrder());

먼저 반환할 보트의 개수 answer를 초기화하고, people 배열을 내림차순 정렬하여 tmp에 담는다.

int light = tmp.length-1;
for(int heavy=0; heavy<=light; heavy++) {
    if((tmp[heavy]+tmp[light]) <= limit) light--;
    answer++;
}

그리고 tmp에서 가장 무거운 사람과 가장 가벼운 사람의 무게 합을 limit와 비교하기 위해선 무거운 사람에서 가벼운 사람 순으로 반복해가며 확인하면 된다. 무거운 사람과 가벼운 사람의 합이 무게제한을 넘으면 무거운 사람 혼자 탑승하고, 무게제한을 넘지 않으면 같이 탑승하기 위해 인덱스를 하나 줄여서 반복문을 종료시키면 된다.

위 내용대로 작성한 코드를 제출하니, 모든 테스트케이스와 효율성 테스트를 정상적으로 통과하였다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        int[] people = {70,50,80,50};
        int limit = 100;
        // int[] people = {70,80,50};
        // int limit = 100;
        // int[] people = {40, 50, 150, 160};
        // int limit = 200;
        // int[] people = {100,500,500,900,950};
        // int limit = 1000;
        // int[] people = {40,40,40};
        // int limit = 120;
        // int[] people = {40,40,40,40,50};
        // int limit = 200;
        // int[] people = {40, 55, 55, 60, 60, 60, 70, 80};
        // int limit = 100;
        // int[] people = {40};
        // int limit = 100;
        // int[] people = {60,60,51,51,100};
        // int limit = 100;
        long start = System.currentTimeMillis();
        solution2(people, limit);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    // 내림차순 풀이
    public static int solution(int[] people, int limit) {
        int answer = 0;
        Integer[] tmp = Arrays.stream(people).boxed().toArray(Integer[]::new); 
        Arrays.sort(tmp, Collections.reverseOrder());
        
        int light = tmp.length-1;
        for(int heavy=0; heavy<=light; heavy++) {
            if((tmp[heavy]+tmp[light]) <= limit) light--;
            answer++;
        }

        return answer;
    }
    // 오름차순 정렬 풀이
    public static int solution2(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        
        int light = 0;
        for(int heavy=people.length-1; light<=heavy; heavy--) {
            if((people[heavy]+people[light]) <= limit) light++;
            answer++;
        }

        return answer;
    }
}

회고

• 문제에서 요구하는 논리를 아이디어로 풀어내는 게 굉장히 어려웠던 문제였다.
• 생각했던 논리대로 풀기 위해 여섯시간을 삽질했지만, 풀지 못하고 투 포인터를 활용하여 정답을 냈다. 다음부턴 문제에서 요구되는 알고리즘이 보인다면 적극적으로 활룡하자.