[프로그래머스] Level2 42885번: 구명보트 (JAVA)

문제

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

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

 

 

풀이코드

package com.algorithm._01_그리디_구현;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class P42885_구명보트 {

    public static void main(String[] args) {
        // write your code here
        P42885_구명보트 main = new P42885_구명보트();
        //System.out.println(main.solution(new int[]{70, 50, 80, 50}, 100));
        //System.out.println(main.solution(new int[]{70, 80, 50}, 100));
        //System.out.println(main.solution(new int[]{130, 80, 50, 30}, 100));
        //System.out.println(main.solution(new int[]{160, 150, 140, 60, 50, 40}, 200));
        System.out.println(main.solution(new int[]{200, 170, 150, 50, 40, 20}, 100));
    }

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

        // 오름차순 정렬
        Arrays.sort(people);

        // 거꾸로간다.
        int start = people.length - 1; // 시작원소
        int end = 0; // 마지막원소

        while (end <= start) {
        	/** 맨 앞의 사람이 보트 제한 무게의 절반 이하가 되면, 무조건 맨 뒤의 사람과 같이 보낼 수 있다.
                절반의 값이 limit 보다 작거나 같으면, 그 다음부터는 해당 원소보다 무조건 작기 때문이다. */
            if (people[start] <= limit / 2) {
                int target = (start - end + 1); 
                answer += (target / 2) + (target % 2); // 몫 + 나머지 
                return answer;
            }

            int sum = people[start] + people[end];

            if (sum > limit) {
                answer++; // start 원소 1개로 개수 +1

                start--; // 앞부분 + 1
            } else {
                // cursor 이동
                start--;
                end++;

                answer++;
            }
        }

        return answer;
    }
}