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

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

---

문제 설명

문제 풀이

풀이 설명

처음엔 깊이든 넓이든 최대로 중복된 라인을 찾을려고 했지만, 코드가 너무 복잡해져 풀이를 찾아보니
각 구간에 마지막 지점에서 미사일을 발사해 제거하는 방식으로 하면 된다는 설명을 보고 풀었다.

주어진 개구간의 마지막 지점을 찾은 후, 해당 구간을 기준으로 미사일을 발사했을 때
개구간에 해당하는 지점을 마킹처리하여 최소값을 찾는다.

코드 작성

        public int solution(int[][] targets) {
            List<int[]> sortTargetByEnd = Arrays.stream(targets).sorted(Comparator.comparingInt(x -> x[1])).collect(Collectors.toList());
            int[] markingMissile = new int[targets.length];
            int launchMissile = 0;

            for(int i = 0; i < sortTargetByEnd.size(); i++) {
                if(markingMissile[i] != 0) continue;
                else markingMissile[i] = ++launchMissile;

                for(int j = i+1; j < sortTargetByEnd.size(); j++) {
                    if(markingMissile[j] != 0) continue;
                    if(sortTargetByEnd.get(i)[1] < sortTargetByEnd.get(j)[0]) break;

                    if(sortTargetByEnd.get(i)[1] > sortTargetByEnd.get(j)[0]){
                        markingMissile[j] = launchMissile;
                    }
                }
            }

            return launchMissile;
        }