[알고리즘] 프로그래머스 - 요격 시스템

이번에 푼 문제는 프로그래머스의 요격 시스템으로, 탐욕 알고리즘을 사용해서 진행했다. 그리디 알고리즘은 각 단계에서 항상 최선의 선택을 하여 최종적으로 최적해를 찾는 알고리즘이다. 그래서 정렬을 우선적으로 사용하여 문제 요소를 적절한 순서로 만들어, 직관적이고 효율적이게 그리디 알고리즘이 동작하게 해야한다. 그래서 그리디 알고리즘에서는 항상 sorting을 먼저 진행해준다.

 

문제

 

문제설명

입출력 설명에서 나와있듯이, y축으로 쭉 뻗어나가는 미사일 요격 시스템을 이용해서 x으로 진행되는 미사일을 요격하는데, 이때 미사일 요격 시스템을 최소한으로 사용하면서 모든 미사일을 다 없애야 해서 최솟값을 구하는 문제이다.

 

 

접근법

이 문제는 탐욕 알고리즘으로 접근하여 해결한다. 그 사유는 아래와 같다.

• 탐욕 알고리즘으로 O(nlogn) 시간 복잡도를 갖게 된다.
• 문제를 잘게 쪼개서 해결하는 구조이다.
• 일단 가장 최선의 선택을 하고 그 뒤를 해결해나가는 구조이다.

정답코드

class Solution {
    fun solution(targets: Array<IntArray>): Int {
        // 시작점을 기준으로 미사일 목록을 오름차순 정렬
        targets.sortBy { it[0] }

        var answer = 0 // 요격한 미사일 수
        var missileEndLimit = -1 // 현재까지 요격한 미사일의 최대 끝점

        for (target in targets) {
            val targetMissileStart = target[0]
            val targetMissileEnd = target[1]

            if (targetMissileStart >= missileEndLimit) {
                // 시작점이 최대 끝점보다 크거나 같으면 미사일 요격
                missileEndLimit = targetMissileEnd
                answer++
            } else {
                // 시작점이 최대 끝점보다 작으면 해당 미사일을 무시
                missileEndLimit = minOf(missileEndLimit, targetMissileEnd)
            }
        }

        return answer
    }
}

 

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/181188