[Programmers] 요격 시스템 - Javascript

INDEX

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

프로그래머스

 

Solution

 

요격의 위치는 실수도 가능합니다. 그리고 주어지는 값 targets는 개구간(s부터 e까지)을 의미하며 s와 e 지점에서 요격하더라도 해당 미사일을 요격할 수 없습니다.

 

모든 미사일을 요격할 수 있는 최소한의 요격 횟수를 구하는 문제입니다.

 

저는 한 개구간과 다른 개구간의 단절이 발생하는 지점을 요격횟수가 추가되는 지점이라 생각했습니다.

예를 들어 [1,3], [3, 5] 라는 두 개구간이 주어진다면 필요한 요격 횟수는 2회입니다.

왜냐하면 <3> 지점에서 구간의 단절이 발생했고 이는 추가적인 요격이 필요하다는 의미입니다.

예를 들어 [1, 6], [2, 5]가 주어진다면 단 한 번의 요격으로 해결이 가능합니다.

왜냐하면 구간의 단절이 발생하지 않았기 때문입니다.

 

처음부터 끝 지점까지 차례대로 구간의 단절이 발생했는지를 찾아내기 위해선 모든 개구간을 시작지점 (오름차순), 끝 지점(오름차순)으로 정렬해야 합니다.

const sortedTargets = targets.sort((a, b) => {
    if (a[0] > b[0]) return 1;
    else if (a[0] < b[0]) return -1;
    else {
      if (a[1] > b[1]) return 1;
      else if (a[1] < b[1]) return -1;
      else return 0;
    }
  });

문제에서 주어진 테스트 케이스인 아래 targets가 주어질 때 위 sortedTargets의 값은 아래와 같습니다.

 

이제 이 배열을 순회하며 구간의 단절을 찾아냅니다.

 

현재의 개구간 : [1, 4] *처음 개구간 요격 횟수가 추가되어야 하므로 구간의 단절로 봄.

[1, 4], [3, 7]에서는 구간의 단절이 발생하지 않았습니다. 3이 4보다 작기 때문입니다.

 

현재의 개구간 : [1, 4]

[4, 5]에서 구간의 단절이 발생했습니다. [1, 4], [4, 5]는 겹치는 부분이 없기 때문입니다.

 

현재의 개구간 : [4, 5]

[4, 8]에서는 구간의 단절이 발생하지 않았습니다. [4, 5]와 겹치기 때문입니다.

 

현재의 개구간 : [4, 5]

[5, 12]에서는 구간의 단절이 발생했습니다. [4,5], [5,12]가 겹치는 부분이 없기 때문입니다.

 

현재의 개구간 : [5, 12]

[10, 14]에서는 구간의 단절이 발생하지 않았습니다. 

 

현재의 개구간 : [5, 12]

[11, 12]에서도 역시 구간이 겹치기 때문에 단절이 발생하지 않았습니다.

 

따라서 정답은 3회입니다.

 

이를 알고리즘으로 구현하면 다음과 같습니다.

let answer = 0;
  let [lastStart, lastFinal] = [-1, -1];
  for (const target of sortedTargets) {
    if (lastStart === -1) { //처음은 구간의 단절이 발생했다고 봄. 최근 개구간 값을 초기화
      answer += 1;
      [lastStart, lastFinal] = target;
    } else {
      const [start, final] = target;
      if (start >= lastFinal && start > lastStart) { //마지막 개구간의 끝 지점보다 현재 시작지점이 크고 현재 시작지점이 마지막 개구간의 시작지점보다 커야 구간의 단절로 봄.
        //단구간 발생
        answer += 1;
        lastStart = start;
        lastFinal = final;
      } 
    }
  }
  return answer;

 

하지만 이 알고리즘에는 치명적인 반례가 존재하는데요..

[[0,4], [5,10], [6,8], [8,9]]입니다.

이 반례에 대한 정답은 3회입니다.

하지만 위 알고리즘대로 푼다면 구간의 단절이 최초 개구간에서 한번, 5 지점에서 한번 해서 2로 나옵니다.

[5, 10]으로 개구간이 있더라도 [6, 8], [8, 9] 에서 구간의 단절이 발생합니다. 이 경우를 위해서 

이전 지점의 끝지점보다 현재 개구간의 끝지점이 작더라도, 이전 지점의 시작지점보다 현재 개구간의 시작지점이 크면 

최근 개구간을 갱신해줘야 합니다.

[5, 10] 으로 잡혀있던 최근 개구간을 [6, 8]로 변경해줘야 한다는 말입니다.

그러면 8 지점에서 구간의 단절 횟수가 추가되므로 정답을 맞출 수 있습니다.

 

 let answer = 0;
  let [lastStart, lastFinal] = [-1, -1];
  for (const target of sortedTargets) {
    if (lastStart === -1) {
      answer += 1;
      [lastStart, lastFinal] = target;
    } else {
      const [start, final] = target;
      if (start >= lastFinal && start > lastStart) {
        //단구간 발생
        answer += 1;
        lastStart = start;
        lastFinal = final;
      } else if (start > lastStart && final < lastFinal) {
        lastStart = start;
        lastFinal = final;
      }
    }
  }
  return answer;
}