코딩연습

[백준 알고리즘] Node.js 1021. 회전하는 큐

니 뽀 2023. 11. 29. 14:29

1. 문제

https://www.acmicpc.net/problem/1021

 

 

 

 

2. 풀이

  • 둘째 줄에 있는 숫자를 뽑아내기 위해 왼쪽이동, 오른쪽이동을 얼마나 최소화할 수 있는지를 구하는 문제이다.
  • 예제 입력 2 를 예시로 들어 8이 나오는 이유를 알아보자.
    1. 10의 크기를 가진 배열이 있다.  / [1,2,3,4,5,6,7,8,9,10]
    2. 2를 뽑아내기 위해  오른쪽 이동과 왼쪽 이동의 수를 비교하고, 왼쪽으로 1번 이동한다.  / [2,3,4,5,6,7,8,9,10,1]
    3. 2를 뽑아낸다.  / [3,4,5,6,7,8,9,10,1]
    4. 9를 뽑아내기 위해 오른쪽 이동과 왼쪽 이동의 최소값을 찾고 오른쪽으로 3번 이동한다.  / [9,10,1,3,4,5,6,7,8]
    5. 9를 뽑아낸다. / [10,1,3,4,5,6,7,8]
    6. 5를 뽑아내기 위해 오른쪽 이동과 왼쪽 이동의 최솟값을 찾고 왼쪽으로 4번 이동한다. / [5,6,7,8,10,1,3,4]
    7. 5를 뽑아낸다. 
    8. 움직인 횟수를 모두 더하면 8 !
const [N, M, ...nums] = require('fs').readFileSync('/dev/stdin')
                         .toString().trim().split(/\s/).map(v => +v);

const queue = Array.from({length : N}, (_, i) => i+1); // N만큼의 크기를 가진 queue
let count = 0; // 이동 횟수를 담을 변수

// 왼쪽으로 이동.
const ReftPush = (arr) => {
  const first = arr.shift();
  arr.push(first);
  return arr;
}

// 오른쪽으로 이동.
const RightPush = (arr) => {
  const last = arr.pop();
  for(let i = arr.length; i > 0; i--){
    arr[i] = arr[i-1]
  }
  arr[0] = last;
  return arr;
}

// 찾아야 하는 값을 담은 M 만큼 반복
for(let i = 0; i < M; i++){
  let target = nums[i];
  while(true){
    if(queue[0] === target) { // queue의 첫번째가 찾아야하는 값과 같다면 반복문 종료.
      queue.shift();
      break;
    }
    
    // 왼쪽 이동과 오른쪽 이동의 최솟값을 찾기 위해 비교.
    const targetIndex = queue.findIndex(item => item === target);
    const rightCnt = queue.length - targetIndex;
    if(targetIndex <= rightCnt) ReftPush(queue);
    else RightPush(queue);

    count++;
  }
}

console.log(count)

 

3. 정리

  • 실버3 으로 올라오자마자 어렵다. 
  • 구글에 검색해보니까 Doubly Linked list를 기반으로  푸신 분이 있었다. 이게 아마 메모리 측면이나 속도 측면에서 더 우수할 것으로 생각된다.