구명보트

유태형·2022년 2월 16일

코딩테스트 프로그래머스

프로그래머스 - Level 2

목록 보기

18/36

문제

문제 분석

배열의 원소에 따라 답이 달라지므로 정렬이 필요해 보인다.

풀이

정렬

원소의 크기에 따라 혼자냐 둘이 타냐가 결정 되기 때문에 정렬이 필요하다. Arrays.sort(배열)로 오름차순으로 정렬 하였다.

최소와 최소

최소의 보트 횟수 즉 가능하면 둘이 태울 수 있어야 한다.
제일 작은 것과 그다음 작은것 순서대로 진행하면 최소한의 보트수로 진행할 수 있을까? 아니다.

최소와 최대

[40,40,50,50,60,60], 100이 주어졌다고 생각해보자 오름차순으로 정렬되어 있으므로 최소 2개씩 부터 카운트하면 (40,40), (50,50), 60, 60순으로 보트가 4개 필요하다. 하지만 최소와 최대로 조합하면 (40,60), (40,60), (50,50)순으로 보트가 3개 필요하므로 보트를 최소한으로 사용할 수 있다.

 	 int left = 0;
 	 int right = people.length - 1;
   
   while(left <= right){
       if(people[left] + people[right] <= limit){
          left++;
          right--;
       }else
           right--;
       
       answer++;
   }

left변수는 최소값을 담고 right변수는 최대값을 담는다.
최소와 최대를 모두 태울 수 있으면 태우고 최소와 최대 둘다 태울 수 없으면 최대만 태운다.(보트의 낭비를 줄이기 위해)

탑승하면 left와 right변수가 한칸 씩 앞으로 이동한다고 생각하면 될 것이다.

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        
        while(left <= right){
            if(people[left] + people[right] <= limit){
                left++;
                right--;
            }else
                right--;
            
            answer++;
        }
        return answer;
    }
}