[프로그래머스] 요격 시스템 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

🤔 해결방법

1. targets를 오름차순으로 배열하고 launch와 [s, e]의 초기값을 설정한다.

2. if 현재 처리 중인 마시일이 파괴되는 시간보다 다음 미사일의 출발시간이 크거나 같다면, launch +1을 하고 현재 미사일의 s,e를 다음 미사일의 값으로 업데이트 한다.

3. else if 다음 미사일의 개구간이 현재 처리 중인 미사일의 개구간 범위에 있다면 현재 미사일의 s,e를 다음 미사일의 값으로 업데이트만 해준다.

 

 

🔑 풀이

처음 문제를 읽었을 때 이해는 했는데 코드로는 어떻게 풀어내야 할 지가 막막했다.😥

그래서 먼저 요격 미사일을 최소로 사용해야 함에 주목했다.

요격 미사일을 최소로 사용하려면 개구간이 겹치는 미사일들은 한 번의 발사로 없애야 했다.

그러기 위해선 먼저 주어진 targets를 오름차순으로 나열하고 개구간을 비교하면서 겹치는 부분을 체크해야 한다.

 

겹치지 않는 경우는 현재 처리 중인 미사일이 끝나는 시간 즉, 파괴되는 시간보다 다음 미사일의 출발시간이 크거나 같은 경우이다.

이 때는 개구간이 겹치지 않기 때문에 미사일을 한 번 더 발사해줘야 한다.

여기서 출발시간이 크거나 "같다면"이 들어가는 이유는 폭격 미사일의 범위가 개구간으로 주어져 양 끝 값은 포함하지 않기 때문이다.

그리고 현재 처리해야 하는 미사일의 개구간을 다음 미사일 값으로 넣어주면 된다.

 

개구간이 겹치는 경우는 미사일을 더 쏠 필요가 없으므로 그냥 현재 처리해야 하는 미사일의 개구간을 다음 미사일 값으로 업데이트 해주기만 하면 된다.

 

따라서 최종 코드는 다음과 같다.

function solution(targets) {
      // 오름차순 정렬
      targets.sort((a,b) => a[0]-b[0]) // [[1,4],[3,7],[4,5],[4,8],[5,12],[10,14],[11,13]]
      let launch = 0 // 요격 미사일 발사 횟수
      let [s,e] = [0,0] // s:미사일의 출발 시간, e: 미사일의 파괴 시간

      for (const missile of targets) {
          // 현재 처리 중인 미사일의 파괴 시간보다 다음 미사일의 출발 시간이 크거나 같다면
          if (e <= missile[0]) {
              launch++ // 발사
              [s,e] = missile // 현재 미사일의 s, e을 다음 미사일의 값으로 업뎃

          // 다음 미사일이 현재 처리 중인 미사일 범위 안에 있다면
          } else if (s <= missile[0] && missile[1] <= e){
              [s,e] = missile // 현재 미사일의 s, e을 다음 미사일의 값으로 업뎃
          }
      }

      return launch;
  }

 

 

예제 1번을 함수에 넣어 변수들의 변화를 체크해보니 좀 더 이해가 잘 갔다.