글 읽기 - [Node JS] 여러 반례를 사용해봤지만, 틀린 부분을 찾지 못하고 있습니다.

hant422 3년 전 0

시간 단축을 시도해보고자 큐를 사용하지 않고 풀이를 시도하고 있습니다. 시도한 풀이 방법은 다음과 같습니다.

순번을 찾고자하는 값의 우선 순위를 N이라고 할 때, 순번은 N보다 큰 우선순위 개수 + 우선 순위 N중에서 찾고자하는 값의 순번 이다.
우선 순위 N중에서 가장 순번이 높은 값은, N보다 높은 우선순위중 가장 낮은 수들 중에서 가장 나중에 오는 수 뒤에오는 N이다.
예를 들어 N이 1일 때, 수열이 5 1 3 1 2 1 4 이면 3번째 1의 우선순위가 가장 높다.
N보다 높은 우선순위중 가장 낮은 수들 중에서 가장 나중에 오는 수를 구하기 위해서 우선순위 9부터 N + 1까지 순회한다.

현재 서치해서 찾을 수 잇는 1966번 문제의 테스트 케이스를 전부 적용해봐도, 알맞은 답은 반환합니다.

하지만 제출하면, 제출 하자마자 "틀렸습니다"가 뜹니다...

살려주세요, 부탁드립니다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const TCS = [];

for (let i = 1; i < input.length; i += 2) {
  TCS.push({
    m: +input[i].split(" ")[1],
    arr: input[i + 1].split(" ").map((c) => +c),
  });
}

function solution({ m, arr }) {
  const val = arr[m];
  const imp = [...Array(10)].map(() => []);

  arr.forEach((n, i) => {
    imp[n].push(i);
  });

  let startIndex = 0;
  let ans = 0;

  for (let i = 9; i > val; i -= 1) {
    if (imp[i].length < 1) continue;
    ans += imp[i].length;

    const index = imp[i].findIndex((num) => num > startIndex);
    if (index < 1) startIndex = imp[i][imp[i].length - 1];
    else startIndex = imp[i][index - 1];
  }

  const size = imp[val].length;
  const valIndex = imp[val].indexOf(m) + 1;
  let index = imp[val].findIndex((num) => num > startIndex) + 1;
  if (index === 0) index = 1;

  ans += ((size - index + valIndex) % size) + 1;
  return ans;
}

console.log(TCS.map(solution).join("\n"));

hant422 3년 전 1

원본 사이트인 http://www.csc.kth.se/contest/...에서 TC를 다운받아 돌렸더니 문제를 발견했습니다.

21번째 줄의 startIndex의 초기값을 0으로 설정한 것이 문제였습니다.

초기값을 -1로 수정하니 문제가 해결됐습니다.

이 방식으로 푸는게 Queue를 쓰는 것보다 훨씬 빠른 결과가 나왔습니다.

댓글을 작성하려면 로그인해야 합니다.