프로그래머스 구명보트 Java

구명보트

재밌게 푼 문제여서 오랜만에 알고리즘 문제 풀이 글을 쓴다.

문제 제한사항으로 무인도에 갇힌 사람이 최대 50,000명까지 주어질 수 있다. 이중 for문을 돌리기만해도 약 25억번 연산이 일어나서 O(N^2)으로는 풀 수 없겠구나 생각했다.

그래도 처음엔 이중 for문을 사용한 방법밖에 떠오르지 않아서 이중 for문에 최대한 if문으로 연산 회수를 줄이기 위해 Map 인터페이스를 활용하는 방법으로 풀고자 했다.

결과는 시간 초과가 나왔다. 허허. 결국 이 문제는 곧 죽어도 한 번의 for문으로 해결해야하는 문제인 것을 확인했다.

그렇게 고민하다가 나온 방법이 있는데 코드로 설명하는게 가장 빠를 듯하다.

import java.util.Arrays;

public class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int lightest = 0;
        for (int heaviest = people.length - 1; heaviest >= lightest; heaviest--) {
            answer++;
            if (people[lightest] + people[heaviest] > limit) {
                continue;
            }
            lightest++;
        }
        return answer;
    }
}

결국 이 문제에서 중요한 것은 남아 있는 사람 중 가장 무거운 사람과 가장 가벼운 사람이 같이 타야한다는 것이다.

이를 구현하기 위해 정렬을 해주었고 lightest 변수에는 가장 가벼운 사람의 위치를 저장하고 for문 안 heaviest 변수에는 가장 무거운 사람의 위치를 저장했다.

역시 그리디 문제가 짜증나긴해도 재미는 있다.