프로그래머스_요격 시스템_day13

 

알고리즘 챌린지 13일 차이다. 오늘은 프로그래머스 Level2로 분류된 요격 시스템 문제를 가져왔다. 
https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

정답률을 보고 좀 어려운가 싶어서 다른 문제를 풀까 했지만 생각보다 쉽게 문제를 풀이할 수 있었다. 백준이나 프로그래머스나 아무리 문제를 풀어보아도 난이도 측정 기준은 아직도 모르겠다. 

이 문제를 푸는 핵심 로직은 겹치는 구간을 일일이 세는 것이 아니라 반대로 끊기는 부분을 찾는 것이다. 로직이 크게 비슷하진 않지만 논리 자체는 비슷할 것 같아서 참고용으로 링크 걸어둔다. 최근에 풀어둔 아날로그시계 문제와 같은 사고방식으로 풀이할 수 있다.

단순하게 생각을 해보자. 이 문제를 풀기 위해서는 한 번의 요격으로 가장 많은 미사일을 격추해야 최소한의 미사일을 발사할 수 있고, 단 하나의 미사일도 놓치면 안 된다. 그렇기 때문에 겹치는 구간마다 요격을 해버리면 요격을 위하여 소모되는 미사일 수가 증가하여 최솟값을 구하기 어려울 것이다. 

그렇다면 기준점을 하나 잡아서 현재 값의 시작점과 이전 값의 끝점을 비교하여 두 미사일의 겹치는 부분이 있는지를 판단하는 것이다. 여기서 체크해야 할 부분은 이과 출신이라면 많이 들어봤을 것이다. 구간의 범위가 폐구간이 아니라 개구간이다. 즉, 시작점과 끝점은 포함되지 않으므로 시작점 = 끝점은 겹치지 않는 것으로 판단해야 한다. 

또한, 요격 가능한 x좌표가 정수가 아닌 실수 범위다. 따라서 요격을 하는 위치가 정확히 정수로 떨어지지 않는다는 말이 된다. 

그렇다면, 모든 미사일의 궤적(= 구간)을 끝 점을 기준으로 오름차순 정렬해 본 다음, 기준값을 이전 미사일의 끝 값으로 잡으면서 targets 배열을 순회해 보자. 

1. 현재 미사일의 시작값이 이전 끝점보다 크다는 말은 무슨 뜻일까? 
바로 이전 미사일과의 접점이 없다는 뜻이 된다. 쉽게 말하면, 겹치던 부분이 끊겼다고 볼 수 있다. 

2. 현재 미사일의 시작점이 이전 끝점과 같다고 하더라도 개구간이기 때문에 겹치는 부분이 없다. 

3. 현재 미사일의 시작점이 이전 끝점보다 작다면 아직 겹치는 부분이 있다는 뜻이다. 

 

★ 여기서 생각해봐야 할 것은 겹치는 부분이 있을 때마다 요격을 해서 카운트해야 할까? 아니다. 오히려 반대다. 
이런 식으로 카운트를 하면 수많은 요격 미사일을 날려야 한다. 
가장 중요한 문제의 조건이 요격 미사일의 출발지점은 실수 범위라는 것이다. 수학을 많이 한 사람도 종종 까먹고 살겠지만, 실수의 범위는 말도 안 되게 크다..;; 즉, 이전과 현재 미사일의 끊김이 판단된 경우에 한 발만 쏜다고 카운트하더라도 
실제로 끊기는 범위 이전에 무조건 요격이 가능하다.
쉽게 말해, 겹치는 부분이 끊긴 순간부터 그 이전에 겹치는 부분에 있는 모든 미사일을 한 번에 요격할 수 있는 실수 범위를 자동으로 고를 수 있다고 생각하는 것이다. 범위가 실수 이기 때문에 가능한 가정이다...
(정수범위였다면 접근을 다르게 했어야겠지만,, )

문제의 예시를 오름차순으로 표현한 그림을 한 번 살펴보자.

위의 그림을 보면서 필자가 설명한 로직대로 끊기는 부분을 기준으로 구간을 찾아보겠다. 

위의 그림을 보면, 오름차순으로 정렬한 그래프를 기준으로 i=0, i=1, i=4인경우 끊김이 발생한다. 
직관적으로 보면, 어느 부분에서 요격을 해야 모든 미사일을 요격할 수 있을지는 감이 올 것이다.

이 말을 다시 하면, 실수 범위 개구간 (1,4), (4,5), (5,12)에서 요격 미사일을 한 발씩 발사하면 모든 공격을 요격할 수 있도록 컴퓨터가 알아서 적당히 요격해 줄 것이라고 판단하는 것이다. 
되게 야매 같다고 생각이 들 수 있지만,,, 실제로 이런 접근으로 풀어야 하는 문제가 많다. 정확한 요격지점을 구할 필요가 없기 때문에 범위를 실수로 주었을 테고, 그 실수 범위 안에서 위 그림처럼 모든 미사일을 요격할 수 있는 경우의 수가 하나라도 존재한다면, 가능한 경우의 수가 있다고 판단할 수 있는 사고방식이 필요하다.

자 이제, 코드로 살펴보자. 지금까지의 설명이 무색할 정도로 간단하다.

Java

정수형 배열을 그대로 해서 문제를 풀이해도 되지만, 필자는 종종 가독성을 위해 클래스를 선언하는 편이다.

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        List<Section> misail = new ArrayList<>(targets.length);
        for(int i=0; i<targets.length; i++) {
            misail.add(new Section(targets[i][0], targets[i][1]));
        }
        
        Collections.sort(misail, ((o1, o2) -> o1.e - o2.e));

        //가장 마지막 종료값
        int end = 0;
        for(int i=0; i<misail.size(); i++) {
            Section now = misail.get(i);
            if(now.s < end) continue; //아직 겹치는 부분이 있다는 뜻
            else { 
                //겹치는 부분이 끊어짐
                answer++; 
                end = now.e;
            }
        }
        return answer;
    }
}

class Section {
    int s, e; 
    public Section(int s, int e) {
        this.s = s;
        this.e = e;
    }
}