[프로그래머스][JAVA][Lv. 2] 요격 시스템

문제 설명

---

제한 사항

---

입출력 예

---

풀이

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        int last = 0;
        
        Arrays.sort(targets, (t1, t2) -> { 
            if (t1[0] == t2[0]) return t1[1]-t2[1]; else return t1[0]-t2[0]; });
        
        last = targets[0][1];
        for (int i = 0; i < targets.length - 1; i++) {
            if (targets[i + 1][0] < last) {
                if (targets[i + 1][1] < last) last = targets[i + 1][1];
            }
            else {
                last = targets[i + 1][1];
                answer++;    
            }
        }
        if (targets[targets.length - 1][0] < last) answer++;
        
        return answer;
    }
}

ㄴ 통과한 풀이

 

import java.util.Arrays;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (t1, t2) -> { 
            if (t1[0] == t2[0]) return t1[1]-t2[1]; else return t1[0]-t2[0]; });
        
        for (int i = 0; i < targets.length; i++) {
            if (targets[i] == null) continue;
            for (int j = i + 1; j < targets.length; j++) {
                if (targets[i][1] > targets[j][0]) {
                    if (j < targets.length - 1)
                        if (targets[j][1] <= targets[j + 1][0]) {
                            targets[j] = null;
                            break;
                        }
                    targets[j] = null;
                }
                else break;
            }
            targets[i] = null;
            answer++;
        }
        
        return answer;
    }
}

ㄴ 테스트 케이스들은 모두 통과하나 채점 실패한 코드

---

후기

처음으로 해결한 레벨2 문제이다. 어떻게 풀지 좋은 생각이 안 나서 꽤 오랫동안 고민하다가 괜찮은 방법이 생각 나서 풀 수 있었다. 그런데 처음에 생각했던 방법대로 풀면 테스트 케이스는 모두 통과하나 채점할 시에 8개 정도 실패가 떴다. 도저히 반례를 찾을 수가 없어서 결국 비슷한 다른 방법을 생각해서 풀었다. 만약 반례를 아시는 분은 댓글 부탁드립니다... 밑에는 제가 사용한 테스트 케이스입니다.

 

(기본 제공 테스트 케이스 제외)

[[3, 6], [2, 4], [5, 6], [1, 3]]  2

[[0, 4], [5, 10], [6, 8], [8, 9]]  3

[[0, 4], [1, 2], [1, 3], [3, 4]]  2

[[0, 4], [0, 1], [2, 3]]  2

[[1, 3], [5, 13], [7, 8], [9, 10]]  3

[[0, 2], [1, 3], [2, 4], [0, 1], [1, 2]]  3

[[0, 2], [1, 3], [0, 4], [1, 4], [0, 2]]  1

[[0, 3], [1, 7], [0, 1], [6, 7], [0, 4], [3, 10]]  2