[백준] 1021번: 회전하는 큐 (JavaScript, node.js)

[백준] 1021번: 회전하는 큐 (JavaScript)

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

1021번: 회전하는 큐

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const input = fs.readFileSync(filePath).toString().split('\n'); //입력값 엔터 기준으로 나누어 배열 생성

const test = input[0].split(' '); //입력 첫째줄
const num_list = input[1].split(' '); //입력 둘째줄

const n = Number(test[0]); //큐 크기
const m = Number(test[1]); //뽑을 숫자 개수

let queue = []; //큐 배열 선언
for (let i = 1; i <= n; i++){ //큐 크기만큼 1~n 값 넣어주기
    queue.push(i);
}

let count = 0; //연산 수

for (let i = 0; i < m; i++){ //뽑을 숫자 개수 m만큼 반복
    //뽑으려는 수의 인덱스가 현재 큐의 크기/2 보다 큰지 작은지 알기 위해 인덱스 구하기
    let num_index = queue.indexOf(Number((num_list[i])));

    while(num_list[i] != queue[0]){ //뽑으려는 수와 큐의 첫번째 원소가 같아질 때까지 반복
        if(num_index <= queue.length / 2){ //만약 뽑으려는 수가 큐의 길이/2보다 작거나 같으면 - 2번 연산
            let qf = queue[0]; //큐 첫번째 원소 저장 (qf - queue first)
            queue.shift(); //shift 연산으로 배열의 모든 요소 왼쪽으로 한칸씩 밀어주기
            queue.push(qf); //push 연산으로 큐 마지막에 다시 첫번째 원소 넣어주기
            count++; //연산 횟수 1추가 
        }
        else if(num_index >= queue.length / 2){ //만약 뽑으려는 수가 큐의 길이/2보다 크거나 같으면 - 3번 연산
            let ql = queue[queue.length - 1]; //큐 마지막 원소 저장 (ql - queue last)
            queue.pop(); //pop연산으로 큐에서 마지막 원소 삭제
            queue.unshift(ql); //unshift연산으로 배열의 모든 요소 오른쪽으로 한칸씩 밀어주기
            //동시에 빈 queue[0]에 (ql) 값 넣어주기
            count++;
        }
    }
    if(num_list[i] == queue[0]){ //뽑으려는 수와 큐의 큐의 첫번째 원소가 같으면 - 1번 연산 
        queue.shift(); //shift 연산으로 배열의 모든 요소 왼쪽으로 한칸씩 밀어주기(첫번째 요소 삭제)
    }
}

console.log(count); //결과 출력

 

• 우선 입력받은 값을 엔터를 기준으로 두 줄로 나누어 배열로 저장했고, 배열로 저장된 각 줄을 공백을 기준으로 나누어 다시 배열로 생성했다.
• 그 중 입력 첫번째 줄의 요소들을 각각 n, m으로 배열 크기, 뽑을 숫자의 개수로 나누어 저장했다.
• 큐를 선언한 뒤 1부터 n까지 숫자를 채워주었고 출력값인 연산 횟수를 저장할 count변수를 선언했다.
• 뽑으려는 수의 위치에 따라 2번 연산을 해야할지, 3번 연산을 해야할지 구현하는 것을 어떻게 해야할지 고민하다가, 현재 큐의 크기를 반 나눈 값을 기준으로 뽑으려는 값이 들어있는 인덱스가 앞에 있으면 왼쪽(2번 연산)으로, 뒤에 있으면 오른쪽으로(3번 연산) 이동하도록 했다. 
• ex) 현재 큐 크기가 8이고, 뽑으려는 값의 인덱스가 3일때 -> 큐 크기의 반(4) 보다 인덱스(3)가 앞에 위치하므로 1과 가까운 왼쪽으로 뽑는 것이 연산 수를 줄일 수 있으므로!
• 그렇게 계속 연산을 진행하여 뽑으려는 수와 큐의 첫번째 원소가 같아지면 첫번째 원소를 삭제한 뒤 왼쪽으로 값을 모두 밀어준다.
• 연산에는 각각 shift와 unshift함수를 사용했는데, 회전하는 큐를 구현하기 위해 각각 첫번째, 마지막 원소를 저장한 후 앞, 뒤로 다시 더해주는 방법을 사용했다. 
• unshift() 연산 시 배열 첫번째 원소가 비게 되는데, 이 때 unshift 내부에 첫번째 원소에 대신 넣을 값을 지정해 주면 넣을 수 있다.

 

* 주석 없는 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const input = fs.readFileSync(filePath).toString().split('\n'); 

const test = input[0].split(' '); 
const num_list = input[1].split(' '); 
const n = Number(test[0]); 
const m = Number(test[1]); 

let queue = []; 
for (let i = 1; i <= n; i++){
    queue.push(i);
}
let count = 0; 

for (let i = 0; i < m; i++){ 
    let num_index = queue.indexOf(Number((num_list[i])));
    while(num_list[i] != queue[0]){ 
        if(num_index <= queue.length / 2){ 
            let qf = queue[0];
            queue.shift();
            queue.push(qf);
            count++;
        }
        else if(num_index >= queue.length / 2){
            let ql = queue[queue.length - 1];
            queue.pop();
            queue.unshift(ql);
            count++;
        }
    }
    if(num_list[i] == queue[0]){
        queue.shift();
    }
}
console.log(count);