학습 키워드

• 그리디

문제 및 해결방법

문제
구명보트

해결 방법

• 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
• 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값
• 그리디 알고리즘을 사용해 최댓값과 최솟값을 더해 limit이 넘는지 넘지 않는지를 판단한다.

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        
        Arrays.sort(people);
        
        int light = 0;
        int heavy = people.length-1;
        int boat = 0;
        
        while(light <= heavy){
            
            if(limit >= people[light] + people[heavy]){
                light++;
            }
            
            heavy--;
            
            boat++;
        }
        return boat;
    }
}

문제
단속카메라

해결 방법

• 우선 도착점인 routes[1]을 기준으로 정렬한다. 도착지점을 카메라 지점으로 삼을 것이다. 먼저, 다음 시작점인routes[0]과 현재 카메라 지점을 비교한다. 만약 카메라 지점이 작다면 카메라를 늘려야한다. 왜냐하면, 다음 시작지점보다 카메라 지점이 이전에 있기 때문이다.

최종 코드

import java.util.*;

class Solution {
  
    public int solution(int[][] routes) {
 
        Arrays.sort(routes, Comparator.comparingInt(a->a[1]));
    
        int cameras = 0;
     
        for(int[] route: routes){
            if(lastCameraPosition < route[0]){
                lastCameraPosition = route[1];
                cameras++;
            }
        }
        return cameras;
    }
}