Coding Test/프로그래머스
[프로그래머스] 요격시스템 JavaScript
okojin
2024. 8. 13. 15:41
문제
그리디 알고리즘
입출력 예
해결 방법
- targets 배열을 e좌표를 기준으로 오름차순 정렬한다 (s값이 e보다 크다면 x좌표가 걸쳐있을 수 없기 때문이다.)
- targets배열 안에 있는 target 중 e값이 가장 작은 target부터 꺼내서 현재 e값과 비교한다.
- target의 s값이 현재 e값보다 크거나 같을 경우 요격 횟수가 1번 더 필요하므로 answer의 값을 1 증가시켜준다.
- answer의 값을 증가시 경우 현재 e의 값을 target의 e 값으로 갱신한다.
- targets배열을 모두 확인할 때 까지 반복한다.
정답 코드
function solution(targets) {
let answer = 0;
targets.sort((a, b) => a[1] - b[1]);
let e = 0;
for (target of targets) {
if (target[0] >= e) {
answer++;
e = target[1];
}
}
return answer;
}