[프로그래머스-JS] level.2 요격 시스템 📌

 

프로그래머스

 

---

📚 나의 풀이 

1시간을 고민하였지만 풀지 못했다.  

아래 풀이는 최대한 풀어본 풀이다 콜백 형식으로 하면  이 문제를 풀기 어렵다.  개구간 범위가 최대 1억이기 때문이다. 

그래도 일단은 풀어보았다. 

 

나의 풀이는 간단하다. 

1. 요격 가능한 모든 x좌표를 구하고 각 x좌표마다 최대 몇발의 미사일을 요격할 수 있는지 객체를 통해서 파악한다. 

2. 최대로 요격할 수 있는 첫 번째x좌표를 구한다.  (Map 객체의 순서보장성을 활용했다)

3. targets.filter를 통해  2번에서 구한 x좌표가 범위에 있으면 해당 미사일을 지운다.  

4. callback 함수를 통해 filter하고 남은 미사일 좌표 배열을 넘겨준다. 

하지만 제출하면  거의 대부분이 시간 초과가 된다. 

개구간 범위가 너무 넓어서 폭격 미사일의 x좌표가 길어질 시  요격 가능한 x좌표가 엄청나게 많이 생성되서 시간이 오래걸리고  targets 배열을 계속 줄여나가면서 콜백하는 형식이라서 더욱더 효율이 떨어진다.  

 

한 마디로 절대 이렇게 풀면 안된다. 

그래도 안 풀린다고  바로 답보기보다는 해보는데 까지는 해볼려고 하였다. 

덕분에 이렇게 풀면서 문제 이해도가 늘었고 놓쳤던 개념들도 다시 공부할 수 있었다. 

 

 

📌 틀린풀이

function solution(targets) {
  let interceptorMissile = 0;

  const callback = (targets) => {
    if (targets.length === 0) return;

    const dict = getDict(targets);
    const MaxInterceptableCoordinate = getCoordinate(dict);

    const restTargets = targets.filter((coordinate) =>
      isInterceptable(coordinate, MaxInterceptableCoordinate)
    );

    if (targets.length !== restTargets.length) {
      interceptorMissile += 1;
      callback(restTargets);
    }
  };
  callback(targets);

  return interceptorMissile;
}

function getDict(targets) {
  const dict = {};
  for (let i = 0; i < targets.length; i++) {
    for (let j = targets[i][0] + 0.5; j < targets[i][1]; j++) {
      dict[j] = (dict[j] || 0) + 1;
    }
  }
  const maxValue = Math.max(...Object.values(dict));
  const newDict = new Map(Object.entries(dict).sort(([a, _], [b, __]) => a - b));
  return { newDict, maxValue };
}

function getCoordinate({ newDict, maxValue }) {
  let indexAtMaxValue;
  for (let [key, value] of newDict.entries()) {
    if (value >= maxValue) {
      indexAtMaxValue = key;
      break;
    }
  }
  return indexAtMaxValue;
}

function isInterceptable(coordinate, MaxInterceptableValue) {
  return !(
    coordinate[1] > MaxInterceptableValue && coordinate[0] < MaxInterceptableValue
  );
}

---

📚 다른 사람 풀이 

 

📌 풀이 1

function solution(targets) {

    let answer = 1;
    // 1. 시작점을 기준으로 오름차순
    targets.sort((a,b) => a[0]-b[0]);
    // 2. 구하기
    let [s, e] = [-1, 100000001]; 

    for(const target of targets){
        const [t_s, t_b] = target;
        if(t_s >= s && t_b <= e)
            [s, e] = [t_s, t_b];
        else if(t_s < e && t_b > e)
            [s, e] = [t_s, e];
        else {
            answer+=1;
            [s, e] = [t_s, t_b];
        }
    }
    return answer;
}

처음 본 정답코드가 이거였는데  "와 이 생각을 못했네 싶었다." 하지만 시간을 돌려도 못했을 것 같다.  

 

이 풀이는 생각보다 단순하다. 

1. 시작점을 기준으로 오름차순 정렬을 한다.  

2. 개구간을 최대 범위로 해놓고  target과 비교한다. 

2-1.  if( 타겟의 시작점 >= s && 타겟의 끝점 <= e) 

현재 폭격 미사일의 범위가 이전 폭격 미사일의 범위 안에 있을 때 

2-2. else if 

현재 폭격 미사일의 범위가 이전 폭격 미사일의 범위에 걸칠 때

2-3 else 

현재 폭격 미사일의 범위가 이전 폭격 미사일의 범위와 겹쳐지는 점이 없을 때 

 

쉽게 말해  targets 배열을 순회하면서 하나하나 폭격미사일의 범위를 확인해서 

이전 폭격 미사일과 현재 폭격 미사일의 범위가 겹치는 점이 있으면 s,e를 수정하고 겹치는 점이 없으면  미사일 + 1을 해주고 현재 폭격 미사일 범위를 [s,e] 에 할당한다.

 

 

📌 풀이 2

function solution(targets) {
    let answer = 0, prev = -1;
    const len = targets.length

    targets.sort((a, b) => a[1] - b[1])

    for (let i = 0; i < len; i++) {
        const [a, b] = targets[i]

        if (prev <= a) {
            prev = b
            answer += 1
        }
    }

    return answer;
}

 이 풀이가 훨씬 간단하고 이해하기 쉽게 코드를 짠것같다.

 

if (prev <= a) {
            prev = b
            answer += 1
        }

이 부분이 핵심이다.  이전 미사일의 범위에서 최대값이 현재 미사일의 범위에서 최소값보다 크거나 같으면 한 번에 요격할 수 없기 때문에 

구분짓는다. 

 

 

이 풀이를 리팩터링을 해보았다. 

가독성을 높이기 위해 변수명을 수정하였고  속도는 조금 떨어지지만 감당가능한 범위라서 for문에서 forEach로 바꾸었다. 

function solution(targets) {
  let interceptorMissileCount = 0;
  let previousTargetMaxX = -1;

  targets.sort((prev, cur) => prev[1] - cur[1]);

  targets.forEach((target) => {
    const [minX, maxX] = target;
    if (previousTargetMaxX <= minX) {
      previousTargetMaxX = maxX;
      interceptorMissileCount += 1;
    }
  });
  return interceptorMissileCount;
}

 

---

 

감사하게도 정답을 남겨주신 분께서 유사문제도 남겨주셨다. 

유사 문제

 

1931번: 회의실 배정