[연습문제] 17. 76 ~ 79 큐
자료구조때 공부한 문제들 다시 복습하면서 완전히 익숙해지기! 그때는 이해 못했던 문제 이번에는 완벽하게 이해하고 넘어가자
76. 큐 만들기
자연수를 저장하는 큐를 만들고자 한다. 입력으로 주어지는 큐 명령어를 처리하는 프로그램을 작성하시오.
명령어의 종류는 총 6가지이며, 아래와 같으며, 명령에 따라 반환된 값을 result 배열에 넣도록 한다.
- enqueue X : 자연수 X를 큐 뒤쪽에 넣는다.
- dequeue : 큐 앞쪽에 있는 값을 제거하고 그 값을 반환한다. 만약 값이 없다면 -1을 반환한다.
- empty : 큐가 비어 있다면 1, 아니면 0을 반환한다.
- size : 큐에 들어있는 자연수 개수를 반환한다.
- front : 큐 앞쪽에 값이 있다면 해당 값을, 없다면 -1을 반환한다.
- back : 큐 뒤쪽에 값이 있다면 해당 값을, 없다면 -1을 반환한다.
const enqueue = (queue, value) => {
queue.push(value);
};
const dequeue = (queue) => {
return queue.length === 0 ? -1 : queue.shift();
};
const empty = (queue) => {
return queue.length === 0 ? 1 : 0;
};
const size = (queue) => {
return queue.length;
};
const front = (queue) => {
return queue.length === 0 ? -1 : queue[0];
};
const back = (queue) => {
return queue.length === 0 ? -1 : queue[queue.length - 1];
};
function answer(cmds) {
let result = [];
let queue = [];
for (let i = 0; i < cmds.length; i++) {
switch (cmds[i].split(" ")[0]) {
case "enqueue":
enqueue(queue, cmds[i].split(" ")[1] / 1);
break;
case "dequeue":
result.push(dequeue(queue));
break;
case "empty":
result.push(empty(queue));
break;
case "size":
result.push(size(queue));
break;
case "front":
result.push(front(queue));
break;
case "back":
result.push(back(queue));
break;
}
}
// 코드 구현 종료 영역
return result;
}
let input = [
["enqueue 1", "enqueue 2", "dequeue", "dequeue", "dequeue"],
[
"enqueue 3",
"enqueue 4",
"enqueue 5",
"enqueue 6",
"front",
"back",
"dequeue",
"size",
"empty",
],
[
"enqueue 7",
"enqueue 8",
"front",
"back",
"size",
"empty",
"dequeue",
"dequeue",
"dequeue",
"size",
"empty",
"dequeue",
"enqueue 9",
"empty",
"front",
],
];
for (let i = 0; i < input.length; i++) {
process.stdout.write(`#${i + 1}`);
console.log(answer(input[i]));
}
//#1[ 1, 2, -1 ]
//#2[ 3, 6, 3, 3, 0 ]
//#3[
// 7, 8, 2, 0, 7,
// 8, -1, 0, 1, -1,
// 0, 9
//]
전에는 메소드를 array의 프로토타입으로 만들었는데, 이번에는 일반 메소드로 만들어보았다.
77. 카드 뽑기
친구와 카드 게임을 하려고 한다.
카드는 총 n장 있으며, 1부터 n까지 번호가 차례대로 붙어 있다.
카드의 순서는 1번 카드가 가장 위에 있고 N번 카드가 가장 아래인 상태로 놓여 있다.
이때 맨 위에 있는 한 장을 빼서 나누고, 그 다음 맨 위에 있는 한 장을 아래로 집어 넣으면서, 모든 카드를 분배할 때까지
카드 한장씩 빼고 넣는 작업을 반복한다.
이러한 규칙으로 분배된 카드의 순서를 알려주는 프로그램을 작성하시오.
입력 값은 자연수가 주어지며, 규칙에 따라 분배되는 카드의 순서를 기록해 배열 형태로 반환하시오.
function answer(n) {
let result = [];
let queue = new Array();
for (let i = 0; i < n; i++) {
queue[i] = i + 1;
}
while (queue.length !== 1) {
result.push(queue.shift());
queue.push(queue.shift());
}
result.push(queue.shift());
return result;
}
let input = [4, 7, 10];
for (let i = 0; i < input.length; i++) {
process.stdout.write(`#${i + 1}`);
console.log(answer(input[i]));
}
// #1[ 1, 3, 2, 4 ]
// #2[
// 1, 3, 5, 7,
// 4, 2, 6
// ]
// #3[
// 1, 3, 5, 7, 9,
// 2, 6, 10, 8, 4
// ]
78. 프린터 출력
새로 구매한 프린터는 우선 순위를 고려해 프린트 결과물을 출력해주기 때문에 아래 규칙으로 동작한다.
현재 등록된 프린트 문서들의 우선순위를 확인하고, 가장 높은 우선순위 문서가 먼저 출력되며
현재 선택된 문서가 가장 높은 우선순위 문서가 아니라면, 취소되고 다시 뒤쪽 순서로 설정돼 추가된다.
만약, 3개의 문서 a,b,c가 대기 상태이고, 중요도가 1,2,3이라면
abc > bca > cab > c출력 > ab > ba > b출력 > a > a출력으로 동작한다.
현재 등록된 문서 우선순위를 보고, 내가 등록한 문서가 언제 출력될 지 계산하는 프로그램을 작성하시오.
입력은 우선순위와 0번부터 시작하는 문서 번호가 주어지고, 주어진 문서번호가 출력될 순서를 반환한다.
function answer(priorities, select) {
let result = -1;
let cnt = 0;
let indexArray = [];
for (let i = 0; i < priorities.length; i++) {
indexArray[i] = i;
}
let max = Math.max(...priorities);
while (1) {
if (priorities[0] < max) {
priorities.push(priorities.shift());
indexArray.push(indexArray.shift());
} else {
priorities.shift();
cnt++;
if (indexArray.shift() === select) {
return cnt;
}
max = Math.max(...priorities);
}
}
return result;
}
let input = [
[[3], 0],
[[3, 4, 5, 6], 2],
[[1, 1, 5, 1, 1, 1], 0],
];
for (let i = 0; i < input.length; i++) {
process.stdout.write(`#${i + 1} `);
console.log(answer(input[i][0], input[i][1]));
}
// #1 1
// #2 2
// #3 5
예전에는 해설을 들어도 이해가 안가던 문제들을 이제는 스스로 쉽게 풀 수 있어졌다. (뿌듯)
79. 대표 선출
마을에 대표를 선출해야 한다.
모두 자신이 대표가 되고 싶어 하며, 아래 규칙을 통해 대표를 선출하기로 하였다.
규칙은 먼저 원탁에 둘러 앉아 시계 방향으로 1번부터 n번까지 번호를 부여한다.
그리고 주사위를 통해 굴러나온 숫자 m의 사람을 제외하고, 그 다음으로 나온 주사위 숫자 k만큼 이동해가며 대표 후보에서 제외시킨다.
이렇게 순회하여 1명이 남을 때까지 반복해 마을의 대표를 선출하기로 하였다.
n, m, k가 주어졌을 때 대표 후보에서 제외되는 번호를 출력해주는 프로그램을 제작하시오.
입력은 n, m, k의 자연수가 주어지며, 대표 후보에서 제외되는 번호를 순차적으로 배열로 반환한다.
function CircularQueue(size) {
this.array = new Array(size);
this.size = size;
this.length = 0;
this.head = 0;
this.tail = 0;
}
CircularQueue.prototype.enqueue = function (element) {
this.length++;
this.array[this.tail++ % this.size] = element;
return true;
};
// dequeue() : 데이터 삭제
CircularQueue.prototype.dequeue = function () {
this.length--;
return this.array[this.head++ % this.size];
};
function answer(n, m, k) {
let result = [];
// 코드 구현 시작 영역
// 1. 원탁에 후보 번호 세팅
let cq = new CircularQueue(n);
for (let i = 1; i <= n; i++) {
cq.enqueue(i);
}
// 2. 첫번째 노드 위치로 설정
cq.tail = cq.head = (n + m - 1) % n;
// 3. k만큼 움직이면서 대표 후보를 제거 (제거된 번호는 result 에 추가)
// 제거된 번호는 result 에 추가
let count;
result.push(cq.dequeue());
while (cq.length != 0) {
count = k - 1;
while (count--) {
cq.enqueue(cq.dequeue());
}
result.push(cq.dequeue());
}
return result;
}
let input = [
[8, 2, 3],
[10, 2, 3],
[20, 5, 7],
];
for (let i = 0; i < input.length; i++) {
process.stdout.write(`#${i + 1}`);
console.log(answer(input[i][0], input[i][1], input[i][2]));
}
// #1[
// 2, 5, 8, 4,
// 1, 7, 3, 6
// ]
// #2[
// 2, 5, 8, 1, 6,
// 10, 7, 4, 9, 3
// ]
// #3[
// 5, 12, 19, 7, 15, 3, 13,
// 2, 14, 6, 18, 11, 9, 8,
// 10, 17, 4, 16, 20, 1
// ]
k만큼 움직일 때, enqueue, dequeue를 하지 않고, head/tail을 움직이게 했었는데,
그러면 삭제된 배열을 알아채지 못하고 그것도 세고 넘어가서 되지 않았다.
꼭 원형큐라고 해서, head,tail로만 조작하려하지않고, 기존 큐 방식대로 enqueue,dequeue를 하는게 좋을 수도 있다는 것을 잊지 말자!
