글 읽기 - 시작 1%부터 틀리는데 모든 예제와 반례를 입력했을 때 맞다고 나옵니다.

wolfye 2년 전 0

차라리 시간초과가 난다면 findIndex에서 문제가 있겠거니 하겠는데 애초에 틀리다고 나오니 너무 모르겠습니다.

다른 질문에 올려주신 반례들을 넣어보았으니 제 역량으론 찾을 수 없어서 코드 봐주시면 감사하겠습니다.ㅠㅠ

/* get input */
const fs = require("fs");

// 백준용
const filePath = fs.readFileSync("/dev/stdin");

// 비쥬얼스튜디오 인풋값
// const filePath = `32 6
// 27 16 30 11 6 23`;

const input = filePath.toString().trim().split("\n");
/* get input end */

/* set param */

/* set param end */

/* solve */

const solution = (input) => {
  "use strict";

  const n = +input[0].split(" ")[0]; // N의 값
  let arr = Array.from({ length: 3 * n + 1 }); // 덱을 구성하려는 배열
  const targetN = +input[0].split(" ")[1]; // 몇개의 개수를 뽑아야 하는지
  const target = input[1].split(" ").map((item) => +item); // 뽑아야 하는 숫자들

  let cnt = 0; // 2, 3 번을 실행하였을 때 숫자를 셀 변수
  let head = n; // 덱의 머리
  let tail = n; // 덱의 꼬리

  const pushFront = (x) => {
    // 덱 앞의 추가
    arr[--head] = x;
  };

  const pushBack = (x) => {
    // 덱 뒤의 추가
    arr[tail++] = x;
  };

  const popFront = () => {
    arr[head] = 0;
    head++;
  };

  const popBack = () => {
    arr[tail - 1] = 0;
    tail--;
  };

  const front = () => {
    return arr[head];
  };

  const back = () => {
    return arr[tail - 1];
  };

  for (let i = 0; i < n; i++) {
    // 먼저 1~N까지의 배열 생성
    pushBack(i + 1);
  }

  for (let i = 0; i < targetN; i++) {
    const query = target[i]; // 찾아야 하는 숫자
    let flag = 0; // 찾으면 그만두게 하기 위함
    while (flag < 1) {
      let findIndex = arr.findIndex((item) => item === query); // 찾고자 하는 숫자가 어디 인덱스 위치에 있는지
      let closeHead = Math.abs(findIndex - head); // 찾고자 하는 인덱스 - 머리
      let closeTail = Math.abs(findIndex - tail); // 찾고자 하는 인덱스 - 꼬리
      //   console.log(front());
      if (front() === query) {
        // 맨 앞의 원소가 찾는 원소이면 뽑고 그만둠
        popFront();
        flag = 1;
        break;
      } else {
        if (closeHead <= closeTail) {
          // 앞쪽에 위치했을 때 , 2번 실행
          pushBack(front());
          popFront();
          cnt++;
        } else if (closeHead > closeTail) {
          // 뒤쪽에 위치했을 때 , 3번 실행
          pushFront(back());
          popBack();
          cnt++;
        }
      }
    }
  }
  //결과값 출력
  console.log(cnt);

  //   }
};

/* solve end */

/* print output */
const output = solution(input);
// for (let i = 1; i <= 1000; i++) {
//   const output = solution(i);
// }
// console.log(output);
/* print output end */

wolfye 2년 전 1

배열을 크게 잡아주니 해결되었습니다

최대인 50 * 50 을 하였을 때 제가 생각한 3 *n +1 으로는 undefined 가 나와 오류가 나서 틀렸던 것 같습니다

  let arr = Array.from({ length: 100000 }, () => 0);
  let head = 5000;
  let tail = 5000;

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

문제

문제

출처

ICPC

시작 1%부터 틀리는데 모든 예제와 반례를 입력했을 때 맞다고 나옵니다.

wolfye 2년 전 0

wolfye 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말