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

📖 문제

프로그래머스

 

 

💡  풀이 방식

• 그리디 (스케줄링)

2차원 int형 배열 targets를 끝나는 시간 기준 오름차순 정렬한다.

끝나는 시간이 같다면, 시작 시간 기준 오름차순 정렬한다.

 

정렬된 배열을 반복문으로 돌면서 "현재 시점의 시작 위치 ≥요격 시스템의 마지막 위치 (end)"인 경우,

요격 시스템의 마지막 위치를 현재 시점의 종료 위치로 갱신하고 정답 + 1한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        // 끝나는 시간 기준 오름차순 정렬. (끝나는 시간 같으면 시작 시간 기준 오름차순 정렬)
        Arrays.sort(targets, (o1, o2) -> {
            if(o1[1] == o2[1])
                return o1[0] - o2[0];
            return o1[1] - o2[1];
        });
        
        int end = targets[0][1];
        answer++;    // 첫 번째로 만들어지는 요격 시스템
        
        for(int[] t : targets) {
            if(t[0] >= end) {    // 요격시스템의 상한보다 오른쪽에 있다면, 새 요격 시스템 추가
                end = t[1];
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

➕ 다른 풀이 방식

- 정렬 방법 : 다양하게 작성할 수 있다.

Arrays.sort(targets, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return Integer.compare(o1[1], o2[1]);
    }
});

 

 

- 다른 접근 방식1) x좌표 기준 오름차순 정렬하고 푸셨다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
    
        Arrays.sort(targets, (a, b) -> a[0] - b[0]); // x좌표 기준 정렬
        
        int cnt = 0;
        int last = -1;
        
        for (int[] t : targets) {
            if (t[0] > last) { // 새로운 요격 미사일 필요
                cnt++;
                last = t[1] - 1; // 해당 미사일로 커버되는 범위
            }
            else if (t[1] - 1 < last) { // 더 작은 범위로 커버 가능한 미사일 필요
                last = t[1] - 1; // 해당 미사일로 커버되는 범위
            }
        }
        return cnt;
    }
}

 

 

- 다른 접근 방식2) 끝나는 구간 기준 오름차순 정렬하셨다.

 

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

 

---

💦 어려웠던 점

1. 그리디 문제인 줄은 알았는데 어떤 기준으로 정렬할지 고민하고,, 이러다가 시간 내에 해결책이 나지 않아 다른 분 풀이를 보았다.

2. 미사인 구간을 동적으로 잘 설정하는 것

 

🧐 새로 알게 된 내용

1. 그리디 문제는 정렬이 중요한 문제가 많구나... 시작이든 끝이든 기준을 하나 잡아 오름차순 정렬하고 그에 따라 코드를 작성하면 된다고 한다!!

2. 시작 구간은 최대, 끝 구간은 최소인 구간으로 잡아야 한다고 한다.

 

[프로그래머스] 요격 시스템 Lv2 JAVA [그리디][엄탱]

 

1회독	2회독	3회독	4회독	5회독
V	240213

---

(참고)

✔ 풀이 참고

프로그래머스 - 요격 시스템(Java)

 

- 비슷한 문제라고 합니당,,

1931번: 회의실 배정