설명

프로그래머스의 구명보트 문제다.

Greedy에 속하며 배낭 문제와 유사하다고 생각할 수 있는데 이번에는 한 개의 배낭이 아니라 여러개의 배낭에 담을 수 있다고 생각하면 될 것이다.

풀이

단순 탐색(실패)

처음으로 시도했던 풀이는 맨 처음 사람부터 두 명씩 뽑아서 무게를 초과하지 않는다면 보트에 태워보내고 초과한다면 한 사람은 다음 보트에 태워 보내는 방식이었다. 하지만 이 경우 [1, 1, 4, 4]의 사람들과 5 무게 제한의 보트가 있을 때 (1, 1), (4), (4) 총 3대의 보트가 필요하다고 계산하지만 실제로는 (1, 4), (1, 4) 총 2대의 보트만 있어도 된다. 즉 이 알고리즘은 틀렸다.

Greedy 탐색 #1(효율성 실패)

두 번째로 생각했던 풀이는 무거운 사람부터 배에 태우고 남은 공간에 태울 수 있는 다른 사람을 찾아보자는 것이었다. 배는 무조건 두 명씩만 태울 수 있기 때문에 가벼운 사람부터 태우면 공간이 낭비된다. 그러므로 무거운 사람을 먼저 태우고 남은 공간에 들어갈 수 있는 최적의 몸무게를 가진 사람을 찾아서 태워서 보내는 것이 핵심이다. 마치 배낭 문제에서 큰 보석을 먼저 넣고 남은 공간에 넣을 수 있는 가장 큰 보석을 찾아서 넣는 것이라 할 수 있다.

이를 기반으로 구현한 코드는 다음과 같다.

import java.util.*;


class Solution {
    public int solution(int[] people, int limit) {
        // 태워야 할 사람은 50,000명까지 주어질 수 있으므로 초기 크기 설정.
        ArrayList<Integer> peoples = new ArrayList<>(50000);
        // {몸무게: 인원 수} 쌍으로 구성된 Map 자료구조.
        // 특정 몸무게의 인원이 몇 명이나 있는지 탐색하기 위함.
        Map<Integer, Integer> indexes = new HashMap<>();
        
        // 주어진 사람들의 몸무게 정보로 자료구조 초기화.
        for(int person: people) {
            peoples.add(person);
            indexes.put(person, indexes.getOrDefault(person, 0)+1);
        }
        
        // 사람들의 수 만큼 ArrayList 객체 크기 축소.
        peoples.trimToSize();
        // Collections의 sort 메서드로 오름차순 정렬.
        Collections.sort(peoples);
        
        int boats = 0; // 사용된 보트 수.
        int sailed = 0; // 구조된 사람 수. 반복문 종료 조건에 사용.
        int bigboyIndex = people.length-1; // 가장 무거운 사람의 인덱스.
        
        // 모든 사람들이 구조될 때까지 반복.
        while(sailed < people.length) {
            // 몸무게가 가장 큰 사람을 bigboy 변수에 할당.
            int bigboy = peoples.get(bigboyIndex--);
            // 이 사람은 보트에 탈 것이기 때문에 Map에서 인원수 감축.
            indexes.put(bigboy, indexes.get(bigboy)-1);
            // 구조된 사람 증가.
            sailed++;
            
            // 만약 이 사람이 마지막 사람이라면 태워보내고 반복문 종료.
            if(sailed >= people.length) {
                boats++;
                break;
            }
            
            
            // 보트의 남은 공간에 탈 수 있는 사람을 smallboy에 할당.
            int smallboy = limit - bigboy;
            // 해당 몸무게의 사람이 없다면 1씩 줄여가며 탐색.
            // 예를 들어 10의 보트에 7이 탔으면 3, 2, 1 순서대로 탐색하는 것.
            while(smallboy > 0 && indexes.getOrDefault(smallboy, 0) < 1) {
                smallboy--;
            }
            
            // 남은 공간에 탈 수 있는 사람이 탐색되었다면 같이 태움.
            if(smallboy > 0) {
                indexes.put(smallboy, indexes.get(smallboy)-1);
                sailed++;
            }
  
            // 보트 출발.
            boats++;
        }
        
        return boats;
    }
}

실행 결과 정확성 검사에서는 성공했지만 효율성 검사에서 모두 탈락하게 되었다. 처음에는 smallboy를 찾을 때 Map 자료구조도 안 쓰고 그냥 Collections의 이진 탐색 메서드로 몸무게를 1씩 줄여가며 탐색했으나 시간 초과가 뜨길래 HashMap을 활용하는 방안으로 변경했지만 역시 실패하고 말았다.

문제에선 약 50,000명의 사람이 주어질 수 있기 때문에 이 smallboy를 초기값부터 1까지 감소시켜가며 탐색하는 과정이 시간을 많이 소모할 것이라고 추측할 수 있다. 그럼 어떻게 해야 할까?

Greedy 탐색 #2(성공)

첫 번째 Greedy 탐색 풀이에서 간과했던 점은 이 문제는 마치 배낭 문제처럼 생각할 수도 있지만 실제로 배낭 문제처럼 풀려고 하면 안된다는 것이다. 왜냐면 문제에서 요구하는 것은 그냥 두 사람씩 배에 태워 보내고 배를 가장 적게 사용하는 것이 목적이지 한 배에 탄 사람이 얼마나 가치있는지를 따지진 않기 때문이다.

더 효율적으로 푸는 방법을 찾던 도중 이 글을 보고 힌트를 얻을 수 있었는데 이는 바로 smallboy를 일일히 탐색할 필요가 없다는 것이다. 위의 풀이에서는 사람의 몸무게를 보석의 가치처럼 생각해서 보트에 탈 수 있는 무게에 최대한 근접한 몸무게를 탐색했지만 어차피 보트에는 두 명만 태워서 보내면 되기 때문에 가장 무거운 사람 한 명, 가장 가벼운 사람 한 명만 태워서 보내면 되는 것이다.

그리고 가장 가벼운 사람이 보트에 탈 수 있는 무게의 절반을 초과한다면 이제 앞으로 보트에 두 명이 탈 수는 없기 때문에 남은 사람을 전부 한 명당 하나의 보트에 태워서 보내면 된다. 그러면 꼭 모든 사람의 몸무게를 탐색하지 않아도 계산이 가능하기 때문에 실행 시간을 획기적으로 줄일 수 있다는 장점이 있다.

이를 기반으로 작성한 코드는 다음과 같다.

import java.util.*;


class Solution {
    public int solution(int[] people, int limit) {
        // 이전과 동일하게 사람들의 몸무게로 초기화.
        ArrayList<Integer> peoples = new ArrayList<>(50000);
        for(int person: people) {
            peoples.add(person);
        }
        
        peoples.trimToSize();
        Collections.sort(peoples);
        
        // 양 쪽(가장 무거운 사람, 가장 가벼운 사람)을 가리키는 포인터. 
        int bigboyIndex = people.length - 1;
        int smallboyIndex = 0;
        
        // 만약 가장 가벼운 사람도 보트에 혼자밖에 못 탄다면 미리 종료.
        if(peoples.get(smallboyIndex) > (limit / 2)) {
            return peoples.size();
        }
        
        int boats = 0;
        // 두 개의 포인터가 서로 교차될 때까지 탐색.
        // 서로 교차된다는 것은 모든 사람을 구조했다는 것.
        while(smallboyIndex <= bigboyIndex) {
            // 가장 무거운 사람을 bigboy 변수에 저장.
            int bigboy = peoples.get(bigboyIndex);
            // 만약 이 사람이 마지막 사람이라면 배에 태워보내고 종료.
            if(bigboyIndex == smallboyIndex) {
                boats++;
                break;
            }
            
            // 가장 가벼운 사람을 smallboy 변수에 저장.
            int smallboy = peoples.get(smallboyIndex);
            // 언급한 대로 배에 두 명 이상 탈 수 없는 경우 최적화.
            if(smallboy > limit / 2) {
                boats += (bigboyIndex - smallboyIndex + 1);
                break;
            }
            
            // 두 사람이 탈 수 있다면 가장 가벼운 사람도 배에 태워 보냄.
            if(bigboy + smallboy <= limit) {
                // 다음으로 가장 가벼운 사람을 가리키기 위해 포인터 증가.
                smallboyIndex++;
            }
            // 다음으로 가장 무거운 사람을 가리키기 위해 포인터 감소.
            bigboyIndex--;
            boats++;
        }
        
        return boats;
    }
}

이를 그림으로 나타내면 다음과 같다.
모든 사람을 배에 태워 보냈다면 가장 무거운 사람과 가장 가벼운 사람을 가리키는 인덱스가 교차되기 때문에 이를 반복문 탈출 조건으로 사용할 수 있다.

만약 가장 무거운 사람들만 계속 배에 타고 남는 공간이 없어서 가벼운 사람들은 배에 타지 못했다고 해도 결국에는 bigboyIndex 포인터가 smallboyIndex 포인터까지 도달하기 때문에 모든 사람을 배에 태워 보낼 수 있다. 이 경우 bigboyIndex와 smallboyIndex가 같다면 모든 사람을 태워 보낸 것이므로 반복문 탈출 조건으로 구현되어 있다.

처음에는 인덱스를 사용하지 않고 양 끝에서 요소를 실제로 삭제하고 참조하기 위해 Deque 인터페이스를 사용했지만 시간 복잡도에 민감한 문제기 때문에 인덱스를 사용하는 방식으로 개선할 수 있었다.

중간부터 두 명 이상 배에 탈 수 없는것이 확정되면 반복을 중단하는 것도 좋은 최적화 전략이었다.

후기

그리고 이번에는 자료구조의 중요성도 알 수 있었는데 내부적으로 배열을 사용하는 ArrayList와 이중 연결 리스트를 사용하는 LinkedList를 활용한 풀이는 위처럼 때에 따라 2, 3배 정도 차이가 나는 것을 볼 수 있다.

아무래도 배열은 상수 시간 내 참조가 가능하지만 연결 리스트는 탐색을 통해 찾아가야하는 만큼 더 시간이 걸릴 것은 확실한데 실제로 오른쪽 풀이는 효율성 테스트를 통과하지 못했다.

반대로 두 개의 포인터를 사용하지 않고 실제로 요소를 삭제하는 코드(결과적으론 실패)에서는 ArrayList가 LinkedList보다 두 배 이상 느리기도 했다. 배열은 삭제하면 나머지 요소를 전부 밀어야 하지만 연결 리스트는 그냥 노드만 새로 이어주면 되기 때문이다. 이처럼 자료구조의 특성을 이해하고 풀이에 따라 적절하게 골라서 사용하는 것도 중요한 능력이 될 것 같다.