[PG] 구명보트 JAVA

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

사람들의 몸무게가 담긴 int[] people, 구명보트가 버틸 수 있는 최대 무게 int limit 가 주어진다.

구명보트를 사용해 모든 사람을 옮기기 위해 최소 몇 번을 태워야 하는지 반환해야한다.

 

1. limit은 사람들 중 가장 무거운 사람보다 항상 크게 주어지기 때문에 모두 옮기는 것은 불가능한 경우는 없다.

2. 보트에는 한 번에 2명 까지만 탈 수 있다. (무게가 남더라도)

 

 

 

풀이 .

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int min = 0;

        Arrays.sort(people);

        // 몸무게가 가장 무거운 사람부터 판단한다.
        for(int max = people.length - 1; min <= max; max--) {
            if(people[max] + people[min] > limit)  // 가장 작은 수와 함께 탈 수 없다면 가장 큰 수는 반드시 혼자 타야만 한다
                answer ++;  // 가장 큰 수 먼저 보낸다. min은 그대로 유지하면서 max만 변경한다
            else {
                answer ++;  // 둘을 같이 보낸다
                min ++;
            }
        }

        return answer;
    }
}

 

처음에 생각한 방식은 위 코드와 달랐다.

 

max 부터 검사를 실시하는 건 동일했지만 min과의 짝은 맨 마지막에 검사했다.

(max, max-1), (max, max-2), ... , (max, min) 순으로 검사했다는 이야기.

 

이유는, 가장 좋은 카드인 min을 처음부터 써버리는 것 보다는.. 무거운 쌍부터 검사해보고 전부 안 될 경우에서야 (max, min) 을 태워 보내는 것이 효율적일 거라고 생각했다. 

(가장 좋은 카드인 min을 최대한 아껴놨다는 느낌? min이 나중에 더 요긴하게 사용될 수도 있으니까)

 

하지만 이런식으로 짰더니 시간초과가 났다.

 

O(n^2) 이고 n=50,000 이기 때문에 가능할 거라고 생각했는데 아니었다.

(50,000 = 5 * 10^4 = 25 * 10^8 = 25 * 1억 이고 25를 상수로 날리면 1억은 1초에 들어오니까. 근데 이게 틀린 계산이었다. 식은 전개하기 전에 n 앞에 상수가 붙어있을때나 날릴 수 있는거지 전부 전개하고 나서 내 마음대로 25를 날려버린 게 틀렸다.)

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

위 코드는 O(n) 으로 무사히 통과가 가능하다.

 

처음부터 (max, min) 조합을 검사하면 min을 너무 빨리 낭비하는 것 아니냐는 처음의 생각은 틀렸다.

 

max 보다 큰 수는 없기 때문에 min 을 남겨둔다고 해도 더 유용하게 쓰일 때는 오지 않는다.

(max, min) <= limit 이라면 ( ?, min ) 에서 ? 자리에 max 가 아닌 다른 어떤 것이 오더라도 전부 ( ?, min ) <= limit 이다.

따라서 max와 min을 바로 같이 보내버려도 정답에 영향을 미치지는 않는다는 것.