프로그래머스
프로그래머스 lv2 - 요격 시스템 (자바)
dragonDeok
2024. 6. 22. 14:37
728x90
문제
풀이
그리디 문제
- 미사일들의 범위가 들어 있는 배열을 미사일의 끝 지점을 기준으로 오름차순 정렬한다.
- 요격 시스템의 시작 값을 0으로 하고 전체 미사일들을 확인하며 요격 시스템의 위치를 업데이트한다.
- 요격 시스템의 위치 <= 미사일의 시작 위치 : 요격 시스템의 위치를 미사일의 끝으로 바꾸고 answer++
- 요격 시스템의 위치 > 미사일의 시작 위치 : 그냥 넘어감
어려웠던 점
그리디적인 사고를 하는게 스스로 부족하다고 느낀다.
범위가 있는 데이터들이 모여 있는 경우 떠올려야 할 접근 방법
- 전체를 어떤 식으로 정렬해야 할까? (시작 위치? or 끝 위치? 어느 방식으로 정렬할까?)
- 전체를 어느 값과 비교해가며 값을 업데이트 해야 할까?
- 어떤 방식으로 업데이트 조건을 처리해야 할까?
코드
import java.util.*;
class Solution {
public int solution(int[][] targets) {
int answer = 0;
Arrays.sort(targets, (o1, o2) -> o1[1] - o2[1]);
int point = 0;
for (int[] a : targets) {
if (point <= a[0]) {
point = a[1];
answer++;
}
}
return answer;
}
}