탐욕 알고리즘 Greedy Algorithm [문제해결전략] ( 프로그래머스 요격 시스템)

 

탐욕 알고리즘(Greedy Algorithm)이란?

현재 상태에서 최선의 선택을 하며 최종적인 해답에 도달하는 방법이다.

 

탐욕 알고리즘 문제를 해결하는 단계

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택절차로 돌아가 위 과정을 반복한다.

 

탐욕 알고리즘은 요격시스템을 풀면서 알게되었다.

처음에는 도통 어떻게 푸는지 몰랐는데 어떻게 푸는지 알게되면 그때부터 쉽게 풀리는 듯 하다.

 

프로그래머스 - 요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        Arrays.sort(targets,(a,b)->a[1]-b[1]); // e를 기준으로 오름차순 정렬
        
        int shortest=-1;
        
        for(int[] target : targets){
            if(target[0]<=shortest) continue;
            shortest = target[1]-1;
            answer++;
        }
        
        
        return answer;
    }
}