요격 시스템 (LV.2)

 

문제

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

프로그래머스

문제 설명
A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

설명

1. 모든 폭격 미사일 구간을 끝점(e) 기준으로 오름차순 정렬.
2. 첫 번째 구간의 끝점 바로 앞(e - 0.1)에서 요격 미사일을 발사.
3. 다음 구간을 확인 시 이전에 발사한 요격 미사일의 위치보다 시작점(s)이 크다면, 해당 구간은 아직 커버되지 않았으므로 새로 요격 미사일을 발사.
4. 모든 구간에 대해 반복, 최소 개수를 구한다.

 

결론만 말하자면, 처음에는 문제를 잘못 풀었다.

S, E 요격 구간에서 정수 단위로 잘라서 가장 높은 빈도의 요격을 수행하는 것으로 오해했다.

하지만 값이 실수 단위인 만큼, 실제로는 간단한 정렬 후 조건에 맞춰서 제거해나가기만 하면 된다.

 

하지만 틀린 과정에서 의미있는 고찰을 두 가지 할 수 있었다.

 

1. Map 구조에서 EntrySet 사용하면서 해당 인자 및 객체를 분석할 수 있었다.

 

HashMap(일반적으로 가장 자주 사용하는 Map 구현체)에서는 주로 반복문 사용시 KeySet을 통해서 키값을 참조하고, 알게 된 키값을 토대로 EntrySet에 요청하여 Value를 얻어오는 줄 알았다.

하지만 실제로는 EntrySet 내부의 Map<K, V>에서 그냥 바로 getKey, getValue를 가져올 수 있다.

Map.Entry<K, V> entrySet

entrySet.getKey();
entrySet.getValue();

//이런 식으로 응용 가능
for(Map.Entry<Integer, Integer> entry : pos.entrySet()) {
    pq.add(new int[] {entry.getKey(), entry.getValue()});
}

 

2. ConcurrentModificationException 문제 발생 

 

for-each 문에서 요소를 제거하면 이를 참조할 수 없는 문제, Iterator를 사용하여 순회 시 이를 극복할 수 있다.

//이런 방식으로 내부의 파라미터 제거 시 for-each 반복 도중 조회할 수 없는 에러 발생
for(int idx : remains) {
    int[] targetArr = targets[idx]; //남아있는 미사일
    if(targetArr[0] < spot && targetArr[1] > spot) {
        remains.remove(idx);
        if(remains.isEmpty()) break SHOT;
    }
}

//해당 방식으로 대체 가능
Iterator<Integer> iterator = remains.iterator();
while(iterator.hasNext()) {
    int idx = iterator.next();
    int[] targetArr = targets[idx]; //남아있는 미사일
    if(targetArr[0] <= spot && targetArr[1] >= spot) { 
        iterator.remove(); // 안전하게 제거
        if(remains.isEmpty()) break SHOT;
        }
    }
}

풀이 1 - 틀림

import java.util.*;

/*
1. Map.Entry<K, V> entrySet 구조 : entry.getKey(), entry.getValue 사용
2. ConcurrentModificationException 문제 발생 : 
for-each 문에서 요소를 제거하면 이를 참조할 수 없는 문제, Iterator 사용할 것.
*/
class Solution {
    public int solution(int[][] targets) {
        int result = 0; //요격 회수
        HashMap<Integer, Integer> pos = new HashMap<>(); //좌표 : 빈도 저장
        HashSet<Integer> remains = new HashSet<>(); //남은 개체수 인덱스
        for(int i = 0; i < targets.length; i++) {
            remains.add(i); //인덱스 채우기
            int start = targets[i][0];
            int end = targets[i][1];
            while(start <= end) {
                if(pos.containsKey(start)) {
                    pos.put(start, pos.get(start) + 1);
                } else {
                    pos.put(start, 1);
                }
                start++;
            }
        }
        
        //높은 빈도 순으로 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                return arr2[1] - arr1[1]; 
            }
        });
        for(Map.Entry<Integer, Integer> entry : pos.entrySet()) {
            pq.add(new int[] {entry.getKey(), entry.getValue()});
        }
        
        //요격 실행
        SHOT:
        while(!pq.isEmpty()) {
            //가장 높은 빈도의 Key(index) 가져오기
            int spot = pq.poll()[0];
            result++;
            // for(int idx : remains) {
            //     int[] targetArr = targets[idx]; //남아있는 미사일
            //     if(targetArr[0] < spot && targetArr[1] > spot) {
            //         remains.remove(idx);
            //         if(remains.isEmpty()) break SHOT;
            //     }
            // }
            Iterator<Integer> iterator = remains.iterator();
            while(iterator.hasNext()) {
                int idx = iterator.next();
                int[] targetArr = targets[idx]; //남아있는 미사일
                if(targetArr[0] <= spot && targetArr[1] >= spot) { 
                    iterator.remove(); // 안전하게 제거
                    if(remains.isEmpty()) break SHOT;
                    }
                }
            }
        
        return result;
    }
}

풀이 2 - 성공

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // 구간을 끝점 기준으로 정렬
        Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));

        int result = 0; // 요격 회수
        double lastEnd = -1.0; // 이전 요격 미사일의 위치를 실수로 관리

        for (int[] target : targets) {
            // 현재 구간의 시작점이 이전에 요격한 미사일의 위치보다 뒤에 있는 경우
            if (target[0] > lastEnd) {
                lastEnd = target[1] - 0.1; // 끝점 바로 앞에서 요격
                result++; // 요격 미사일 발사
            }
        }

        return result;
    }
}