[백준] 1021번: 회전하는 큐 (JavaScript)
https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
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);
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1934번: 최소공배수 (JavaScript, node.js) (0) | 2024.05.27 |
---|---|
[백준] 11866번: 요세푸스 문제 0 (JavaScript, node.js) (0) | 2023.06.05 |
[백준] 11279번: 최대 힙 (JavaScript, node.js) (0) | 2023.06.05 |