Coding Test/프로그래머스

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

okojin 2024. 8. 13. 15:41

문제

그리디 알고리즘

입출력 예

해결 방법

  1. targets 배열을 e좌표를 기준으로 오름차순 정렬한다 (s값이 e보다 크다면 x좌표가 걸쳐있을 수 없기 때문이다.)
  2. targets배열 안에 있는 target 중 e값이 가장 작은 target부터 꺼내서 현재 e값과 비교한다.
  3. target의 s값이 현재 e값보다 크거나 같을 경우 요격 횟수가 1번 더 필요하므로 answer의 값을 1 증가시켜준다.
    1. answer의 값을 증가시 경우 현재 e의 값을 target의 e 값으로 갱신한다.
  4. 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;
}