[42885] 구명보트

✔ 구명보트

[프로그래머스 42885]

문제 분석하기

몸무게를 오름차순으로 정렬한 후, 반복문으로 탐색하며 같이 구출될 수 있는지 확인하도록 함

예) [50, 50, 70, 80]

i	index	함께 구출이 가능한지	answer
3	0	80 + 50 >= 130	1
2	0	70 + 50 >= 120	2
1	0	50 + 50 >= 100	3
0	0

손으로 풀어보기

1. 몸무게를 오름차순으로 정렬
2. 맨 뒤 몸무게부터 시작하여 반복문으로 탐색하며 같이 구출될 수 있는 몸무게가 있는지 확인
   • 구출될 수 있는 몸무게는 앞에서부터 탐색
3. 구명보트의 갯수 반환

슈도코드 작성하기

people(사람들의 몸무게를 담은 배열)
limit(구명보트의 무게 제한)
answer(구명보트 개수의 최솟값)
people 오름차순 정렬
index(앞에서부터 탐색하는 인덱스) = 0
for(i -> i는 people.length부터, i가 index보다 큰 동안) {
    if(people[i] + people[index] <= limit) {
        index++;
        answer++;
    }
    else {
        answer++;
    }
}
answer 반환

코드 구현하기

/**
 * 42885) 구명보트
 */
public class K004_42885 {
    // people(사람들의 몸무게를 담은 배열)
    // limit(구명보트의 무게 제한)
    public int solution(int[] people, int limit) {
        // answer(구명보트 개수의 최솟값)
        int answer = 0;
        // people 오름차순 정렬
        Arrays.sort(people);
        // index(앞에서부터 탐색하는 인덱스) = 0
        int index = 0;
        for (int i = people.length - 1; i >= index; i--) {
            // 두 몸무게가 무게 제한보다 작거나 같다면
            if (people[i] + people[index] <= limit) {
                // 함께 구출 가능하므로 index, answer 증가
                index++;
                answer++;
            } else {
                // 함께 구출 불가능하므로 answer만 증가
                answer++;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K004_42885 solution = new K004_42885();

        int[] people = { 70, 50, 80, 50 };
        int limit = 100;

        int result = solution.solution(people, limit);

        System.out.println(result);
    }
}