https://www.acmicpc.net/problem/2164
썸네일대로 어두워졌던 문제 ,,,,
function solution(n) {
let queue = Array.from({ length: n }, (_, i) => i + 1);
while (queue.length > 1) {
queue.shift();
queue.push(queue.shift());
}
return queue[0];
}자바스크립트의 배열과 내장 함수를 이용하여 간단하게 구현이 가능하다.
테스트케이스도 잘 통과하지만.... 막상 제출해보면 시간 초과가 뜬다.
자바스크립트의 shift는 배열의 첫번째 값을 삭제하고, 2번째부터 마지막까지의 값을 앞으로 당겨서 새로운 배열을 만드는 함수이다. 배열이 길어지면 길어질수록 시간 효율이 안 좋아지는 것 ..
문제에서 주어진 n값의 범위가 50만까지이니 시간 초과가 뜨는 게 당연하다.
시간 복잡도를 낮추기 위해 shift함수를 사용하지 않고, 큐를 직접 구현해야한다.
큐 뿐만 아니라 여러 함수들도 함께 구현해야하기 때문에 모든 기능을 캡슐화하기 위해 class를 이용하는 것이 좋다!!
constructor() {
this.queue = {};
this.start = 0;
this.end = 0;
}먼저 constructor를 이용하여 큐를 만들고, start,end (인덱스 값)을 초기화 해준다.
인덱스 값을 따로 지정하는 이유는 큐를 linked-list와 비슷한 형태로 구현하기 위함이다.
참고로 배열은 연속된 메모리 공간에 데이터가 저장되는 것이고, linked-list는 각각 저장되어있는 데이터의 메모리 주소가 이어져있는 형태이다. 그렇기 때문에 값의 추가, 삭제가 잦은 경우에는 linked-list를 사용하는 것이 훨씬 효율적이다. 앞쪽 값을 삭제하는 경우에도 배열은 뒷부분을 모두 이동시켜야하지만, linked-list는 독립적으로 삭제가 가능하다.
객체와 인덱스 값을 이용하여 구현하는 이 방법은 정확히는 linked-list는 아니다. 하지만 각각의 값이 독립적으로 저장되고 인덱스로 연결된 것처럼 linked-list와 비슷한 원리로 동작하기 때문에 알아두면 좋다!!🤩
로직 이해하기
start는 첫번째 요소의 key 값, end는 다음에 값이 들어갈 인덱스(마지막 key값+1)이 된다.
{
0: 3,
}
// start = 0, end = 1
{
0: 3,
1: 5,
}
// start = 0, end = 2
{
0: 3,
1: 5,
2: 7,
}
// start = 0, end = 3
이렇게 값이 추가되어있는 상태에서 값을 하나 제거하면
{
1: 5,
2: 7,
3: 0,
}큐는 이렇게 되고, start=1, end=3가 된다.
삭제한 후에 값을 추가해보자.
{
1: 5,
2: 7,
3: 0,
4: 9,
}그러면 start=1, end=4가 된다.
값을 삭제하고, 인덱스를 옮기는 것만으로 선입선출의 형태를 구현할 수 있는 것이다 !!
큐 구현하기
enqueue
값을 추가하는 경우에는 end 인덱스에 새로 넣을 값을 할당해주고, end 인덱스를 증가시키면 된다.
enqueue(x) {
this.queue[this.end++] = x;
}dequeue
값을 삭제하는 경우에는 객체에 start인덱스로 접근하여 delete한 뒤, start 인덱스를 증가시키면 된다.
삭제한 값을 다시 사용해야해서 리턴값으로 추가했다!
dequeue() {
const value = this.queue[this.start];
delete this.queue[this.start++];
return value;
}length
꼭 필요한 것은 아니지만, 코드의 가독성을 위해 추가했다.
length() {
return this.end - this.start;
}문제 풀이하기
const q = new Queue();
for (let i = 1; i <= n; i++) {
q.enqueue(i);
}구현한 클래스에 대해서 인스턴스를 만들고, 주어진 카드의 수만큼 큐에 값을 추가한다.
while (q.length() > 1) {
q.dequeue();
q.enqueue(q.dequeue());
}이제 카드가 1장 남을 때까지 가장 위에 있는 카드를 버리고, 그 다음에 가장 위에 있는 카드를 가장 아래로 옮기는 것을 반복하면 된다.
반복이 완료된 후에는 큐에 남아있는 값을 리턴하면 되는데, 객체의 인덱스는 항상 문자열이므로 값을 가공할 필요가 있다.
앞서 end 인덱스는 마지막 key값+1이기 때문에 실제 마지막 값의 key값은 end-1이 된다. 그리고 end-1의 값은 number타입이기 때문에 문자열로 변환해줘야한다.
return q.queue[(q.end - 1).toString()];
이 모든 걸 한 줄로 정리하면 이렇게 된다.
전체 코드
class Queue {
constructor() {
this.queue = {};
this.start = 0;
this.end = 0;
}
enqueue(x) {
this.queue[this.end++] = x;
}
dequeue() {
const value = this.queue[this.start];
delete this.queue[this.start++];
return value;
}
length() {
return this.end - this.start;
}
}
function solution(n) {
const q = new Queue();
for (let i = 1; i <= n; i++) {
q.enqueue(i);
}
while (q.length() > 1) {
q.dequeue();
q.enqueue(q.dequeue());
}
return q.queue[(q.end - 1).toString()];
}
const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let n;
rl.on("line", (line) => {
n = Number(line);
rl.close();
}).on("close", () => {
console.log(solution(n));
});
