1021. 회전하는 큐

고민했던 부분:

18258문제 풀었을 때 shift()쓰면 시간초과나서 포인터를 이동시키면서 head랑 tail위치를 기록함

해당 문제는 shift()사용해도 시간초과 안남 왜? 오히려 포인터로 하려고 하면 firstIdxOut이랑 moveLeft, Out할 때 꼬임

shift 사용 유무 판단 기준

• 보통 알고리즘 문제의 제한 시간은 1~2초
• 1초에 약 1억 번($10^8$)의 연산을 처리

---

• 18258번 (큐 2):
  • 명령의 수 N: 최대 2,000,000 ($2 \times 10^6$)
  • shift()를 쓰면 $O(N)$의 시간이 걸립니다.
  • 만약 200만 번 모두 pop 명령이 들어온다면? $2,000,000 \times 2,000,000 = 4,000,000,000,000$ (4조 번!)
  • 결과: 1억 번을 아득히 넘어가므로 시간 초과.
• 1021번 (회전하는 큐):
  • 원소의 개수 N: 최대 50, 뽑으려는 개수 M: 최대 50
  • 한 숫자를 뽑기 위해 최악의 경우 50번 shift()를 한다고 쳐도, $50 \times 50 = 2,500$번 정도입니다.
  • 결과: 1억 번에 비하면 2,500번은 찰나의 순간입니다. 따라서 여유롭게 통과.

실패코드

for (let m = 0; m < M; m++) {
  let target = posList[m];

  if (target === dequeue[0]) {
    firstIdxOut();
  } else if (target < dequeue.length / 2) {
    moveLeft();
  } else if (target > dequeue.length / 2) {
    moveRight();
  }
}

console.log(cnt);

타겟이 맨 앞으로 올 때까지 moveLeft()나 moveRight()를 계속 수행해야하는데, 비교하고 한 번 밖에 수행 안함.

성공코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const posList = input[1].split(" ").map(Number);

const dequeue = Array.from({ length: N }, (_, i) => i + 1);
let cnt = 0;

function firstIdxOut() {
  dequeue.shift();
}

function moveLeft() {
  let firstNum = dequeue.shift();
  dequeue.push(firstNum);
  cnt++;
}

function moveRight() {
  let lastNum = dequeue.pop();
  dequeue.unshift(lastNum);
  cnt++;
}

for (let m = 0; m < M; m++) {
  let target = posList[m];
  let targetIdx = dequeue.indexOf(target);
  let halfIdx = dequeue.length / 2;

  while (dequeue[0] !== target) {
    if (targetIdx <= halfIdx) {
      moveLeft();
    } else {
      moveRight();
    }
  }

  firstIdxOut();
}

console.log(cnt);

5430. AC

팁

[1,2,3,4]
[42]
[1,1,2,3,5,8]
[]

다음과 같이 들어오는 문자열 배열로 바꾸기

1. JSON.parse 사용

   let arr = JSON.parse(input[i * 3 + 3]);

2. split과 slice사용

   let arr = input[i * 3 + 3].slice(1, -1).split(",").map(Number);

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

// R: 배열에 있는 수 뒤집기
// D: 첫번 째 수 버리기, 빈 배열의 경우 에러

const T = input[0]; // 테스트 케이스의 개수

function AC(line, arr, n) {
  let command = line.split("");
  let startIdx = 0;
  let endIdx = n - 1;
  let isReverse = false;

  // 뒤집혔다면 endIdx있는 곳이 앞쪽 -> D: endIdx--
  for (let char of command) {
    if (char === "R") {
      isReverse = !isReverse;
    } else if (char === "D") {
      if (startIdx > endIdx) {
        return "error";
      }

      if (isReverse) {
        endIdx--;
      } else {
        startIdx++;
      }
    }
  }

  let result = [];
  if (isReverse) {
    for (let i = endIdx; i >= startIdx; i--) {
      result.push(arr[i]);
    }
  } else {
    for (let i = startIdx; i <= endIdx; i++) {
      result.push(arr[i]);
    }
  }

  return "[" + result.join(",") + "]";
}

for (let i = 0; i < T; i++) {
  let p = input[i * 3 + 1];
  let n = Number(input[i * 3 + 2]);
  let arr = JSON.parse(input[i * 3 + 3]);
  // let arr = input[i * 3 + 3].slice(1, -1).split(",").map(Number);
  // console.log(arr);
  console.log(AC(p, arr, n));
}