[프로그래머스] 요격 시스템

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

프로그래머스

---

초기 풀이 방법 (통과 ❌)

• targets의 값끼리 중복되는 최소 구간을 저장하기 위해 duplRangeList 생성
• targets의 값을 하나 씩 확인하며 duplRangeList와 겹치는 구간이 있으면 최소 구간으로 갱신
• duplRangeList와 겹치는 구간이 없으면 target값을 duplRangeList에 추가
• 최종적으로 duplRangeList의 길이 반환

 

초기 풀이 방법 코드(통과 ❌)

import java.util.ArrayList;

class Solution {
    
    public int solution(int[][] targets) {
        
        
        ArrayList<int[]> duplRangeList = new ArrayList<>();
        
        for (int[] target: targets) {
            
            int s = target[0], e = target[1];
            
            boolean isDupl = false;
            for (int[] duplRange: duplRangeList) {
                
                if ( (e <= duplRange[0]) || (s >= duplRange[1]) )   continue;
                
                // 겹치는 구간이 있을 경우 최소구간으로 업데이트
                isDupl = true;
                duplRange[0] = Math.max(s, duplRange[0]);
                duplRange[1] = Math.min(e, duplRange[1]);

                break;
            }
            
            if (isDupl)   continue;
            
            // 겹치는 구간이 없을 경우 중복구간 리스트에 target 추가
            duplRangeList.add(target);    
        }
        
        
        return duplRangeList.size();
    }
}

 

자바 배열 정렬 메서드 Arrays.sort() 을 사용하면 평균 : O(nlog(n)) / 최악 : O(n^2) 의 시간복잡도를 갖는다.

target의 최대 길이가 500,000으로 작지 않은 편이기 때문에 최악의 시간복잡도를 생각해서 정렬을 쓰고 싶지 않았다.

 

물론 풀다보니 이 코드도 for문 안에 for문이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 갖지만..

초기에는 시간복잡도를 생각해서 정렬 메서드를 사용하기 싫었다(이유 없는 고집)

 

이 풀이는 총 11개의 테스트 케이스 중 4개만 통과했고, 아직까지 반례를 찾지 못했다😰.

반례를 알고계시는 분 댓글 부탁드립니다..!

 

---

 

정렬을 사용한 풀이 방법 (통과 ⭕)

target의 가장 마지막 구간에서 요격 한다고 생각!

• 각 targets값의 두 번째값을 기준으로 오름차순 정렬 
• targets을 반복 하며
• 현재 target의 시작 값과 현재 미사일을 발사하는 최대위치(사실 개구간이라 포함되지는 않는다)를 비교
• target의 시작 값 > 미사일을 발사하는 최대위치 : 범위에 포함되므로 또 다른 미사일을 더 발사하지 않아도 됨 -> 미사일 개수 그대로
• target의 시작 값 <= 미사일을 발사하는 최대위치 : 범위에 포함되지 않으므로 미사일을 더 발사해야함 -> 미사일 개수 + 1
• 발사한 미사일 개수 return

 

정렬을 사용한 풀이 코드(통과 ⭕)

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        
        // targets 값들의 2번재 인자 값을 기준으로 오름차순 정렬
        Arrays.sort(targets, (o1, o2) -> {  return  o1[1] - o2[1];  });
        
        
        int missileCnt  = 0;  // 현재까지 요격에 사용된 미사일 개수
        int maxShotVal  = -1; // 미사일 발사 위치 최대값 (개구간이라 포함은 되지 않음)
        for (int[] target: targets) {
            
            if (target[0] < maxShotVal) continue;
            
            missileCnt++;
            maxShotVal = target[1];
            
        }
        
        
        return missileCnt;
    }
}