[Java] 프로그래머스 구명보트

1. 문제파악

 

구명보트로 탈출을 하는데 여기서 조건을 잘 살펴봐야한다.

 

1. 무게 제한을 넘어가면 보트를 같이 탈 수 없다.

2. 구명보트는 작아서 최대 2명만 탈 수 있다.

 

항상 문제를 잘 보고 분석하는 방법으로 해결해야하는데 매일 대충보고 풀어 이번에도 오래 걸렸다.

최대 2명만 탈 수 있다.. 문제를 잘 보도록 하자

그렇다면 보트의 최솟값을 구할려면 어떻게 접근해야할까?

1. 정렬 후 앞에서 부터 하나씩 찾기

만약 [70,50,80,50]이라고 생각하자. 정렬 후 배열은 [50,50,70,80]이 된다.

앞에서 부터 하나씩 값을 가져오고 인원이 2명이 넘거나 무게가 초과되면 다음 인덱스로 넘어가게 구현한다.

하지만 이게 가장 최솟값을 구하는 방법일까? 

[40,40,40,200,200,200]와 제한무게 240kg의 경우를 생각해보자. [40,40],[40,200],[200],[200]으로 4개가 필요하다.

2. 정렬 후 뒤에서 부터 하나씩 찾기

위와 같은 경우에서 반대로 생각했다. 마찬가지로 [200],[200],[200,40],[40,40]으로 4개가 필요하다.

2. 정렬 후 맨 뒤와 맨 앞에서 하나씩 가져오기

[200,40],[200,40],[200,40]으로 3개가 된다. 최솟값을 구할 수 있었다.

사실 위의 방법으로 문제를 풀려했지만 계속 오류가 났다.

그래서 테스트 케이스를 더 추가해보니 내가 구현한 방법은 정답이 아니라는 것을 알았다.

 

이제 코드로 구현해보자

2. 구현

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int start = 0;
        int end = people.length - 1;
        
        //정렬
        Arrays.sort(people);

        //만약 첫번째 사람이 limit보다 몸무게가 많이 나가면 사람수마다 보트가 필요
        if (people[start] >= limit) {
            return people.length;
        }

        while (start <= end){
            //보트 사용
            answer += 1;
            //가장 무거운 사람부터 시작, 하지만 가벼운 사람이 동승가능하면 같이 태우기
            if(people[start] + people[end] <= limit){
                start += 1;
            }
            //안되면 무거운 사람만 태우기
            end -= 1;
        }
        return answer;
    }
}

효율성을 위해 맨 처음 if문으로 몸무게가 가장 적은 사람이 limit을 넘어간다면 배열의 개수를 return 해주었다.

 

가장 무거운 사람과 가장 가벼운 사람을 뽑은 다음 limit을 넘어가는지 구한다.

만약 넘지 않으면 start+1을 해서 가벼운 사람을 추가한다. 그리고 2명까지 태울 수 있으므로 end-1을 해준다.

3. 마무리

사실 문제보고 되게 쉽다고 생각했는데 설명도 제대로 안읽고 알고리즘도 맞지않아 정신차리고 해야겠다는 생각이 들었다. 실제 테스트를 하는 것 처럼 집중해서 문제를 풀어야겠다.