.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입력 1
6
Plain Text
복사
예제 출력 1
4
Plain Text
복사
My solution
주어진 설명대로 로직을 짜면 아래와 같이 아주 쉽게 짤 수 있다.
function solution(i) {
let nums = i.toString().trim().split("\n");
let cards = Array.from({ length: nums }).map((_, i) => (i + 1).toString());
while (cards.length > 1) {
cards.shift();
cards.push(cards.shift());
}
console.log(cards[0]);
return cards[0];
}
test("solution", () => {
expect(solution("6")).toBe("4");
});
JavaScript
복사
그런데 제출하면 시간 초과가 나온다.
아래 글을 보고 힌트를 얻었다. 일단은 성능 고려를 안하고 통과하면 그때부터 리팩터링하면서 고려하는 편인데 아예 시간초과로 통과를 시키지 않으니 검색해보았다.
이럴 때는 규칙성 발견으로 에지 케이스 처리를 하는 것이 좋다고 한다.
1234가 있을 때 1을 버리고 2를 뒤로 보내고 3을 버리고 끝난다.
12345가 있으면 1을 버리고 2를 뒤로 보내고 3을 버리고 4를 뒤로 보낸다음 5를 버리고 끝난다.
즉, 홀수번째(0부터 시작이지만)에 있는 카드들은 버려지게 된다.
따라서 아래와 같이 짤 수 있다.
function solution(i) {
let nums = i.toString().trim().split("\n");
let cards = Array.from({ length: nums })
.map((_, i) => i + 1)
.filter((_, i) => !((i + 1) % 2));
console.log(cards);
while (cards.length > 1) {
cards.shift();
cards.push(cards.shift());
}
console.log(cards.pop());
return;
} ...
JavaScript
복사
여전히 시간 초과가 나온다.
그럼 배열의 shift() 연산의 시간복잡도가 O(n)인 이유밖에 없을 것 같다. 배열 맨 앞을 뽑으면 뒤의 원소들을 한칸씩 다 앞당겨줘야하기 때문이다. 큐는 디큐할 때 시간복잡도가 O(1)로 알고 있다. 성능을 찾아보니
결론만 보면 아래와 같다.
큐로 구현해야만 통과하겠다는 생각이 들었다. js에서 큐 구현을 강제하기 위한 게 아니었을까 싶다.
그런데 큐를 연결리스트와 배열로 구현하는 방법이 있는데 처음에는 연결리스트로 구현하는 것을 먼저 찾아서 그걸로 하려고 했다가 연결리스트는 일반적으로 배열보다 느리다는 말을 듣고 연결리스트와 배열이 어떤 성능상의 차이가 있는 것인지 찾아봤다.
운영체제 강의를 들으면서 배웠던 내용인데 일반적으로 사용하려는 메모리 값들은 캐싱해두고 관련된 값까지 같이 캐싱되어 있어 빠르게 접근해 사용할 수 있으나 만약 캐싱되어 있지 않은 값을 요구하면 메모리에 다시 접근해서 값을 가져오게 되므로 더 많은 시간이 소요된다는 것이다. 이를 Cache locality와 Cache hit을 알면 이해할 수 있다.
cache hit: 1과 같이 지역성을 활용하기 위해 캐쉬에 저장해놓은 메모리에 CPU가 참조하고자 하는 메모리가 있다면 cahce hit, 캐쉬 적중이라고 한다. 반대의 개념은 cache miss.
cache locality: 운영체제에선 물리적으로 근접한 위치의 데이터가 주로 활용되기 때문에 미리 캐쉬에 넣어둠으로써 CPU의 성능을 향상시킨다. 배열은 물리적으로 연속된 공간에 데이터를 저장하기 때문에 이러한 locality를 잘 활용할 수 있다.
따라서 배열로 큐를 구현해보기 위해서 아래의 사이트들을 참고했다.
deque 하는 부분이 일반 배열과 다르기 때문에 이것을 잘 이해해야 한다. 비어있을 때는 null을 리턴하고,
비어있지 않으면 먼저 한칸 이동시킨다.
마지막에는 _element의 맨 앞의 값을 제외하고 다시 만든다. 이 배열을 기준으로 하면 맨 앞의 값을 가리키는 인덱스인 _offset은 0으로 다시 초기화된다. 이 방식만 사용하게 되면 너무 느려서 추가 처리가 필요하다.
성능 개선을 위해 필요한 로직을 차례대로 보면,
deque : 만약 큐에 5개가 들어있고 offset이 0이고 1만큼 더해져서 1이 되었을 때 if(this.offset * 2 < this._element.length)에서 2 < 5가 되면 맨 앞의 값만 반환하고 큐를 다시 만들지 않는다.
deque : 계속 큐에 5개가 들어있고 offset이 1이고 1만큼 더해져서 2가 되었을 때 if(this.offset * 2 < this._element.length)에서 4 < 5가 되면 맨 앞의 값만 반환하고 큐를 다시 만들지 않는다.
deque : offset은 이제 2가 된 상태이고 first는 현재 offset인 2의 위치에 있는(가장 앞에 있는) 값이 된다. offset은 3으로 증가시키고 이때 if(this.offset * 2 < this.element.length) 에서 3 * 2 < 5 로 false가 된다.
즉, 큐의 중간까지는 위의 방식으로 성능상의 이득을 볼 수 있고 그 다음부터는 slice를 통해 배열을 잘라서 재정비한다.
class Queue {
constructor(elements) {
// * : 처음에 배열을 넣어줄 수 있다.
this._elements = Array.isArray(elements) ? elements : [];
// * : _offsset은 큐의 맨 앞의 값의 인덱스를 가리킨다.
this._offset = 0;
}
enqueue(element) {
this._elements.push(element);
return this;
}
dequeue() {
if (this.isEmpty()) return null;
// 맨 앞의 값을 가지고 _offset을 한칸 이동
const first = this.front();
this._offset += 1;
// 큐의 중간까지는 offset 만으로 처리가 가능하다. 성능개선, 어차피 멤버변수는 정보은닉으로 접근불가
if (this._offset * 2 < this._elements.length) return first;
// only remove dequeued elements when reaching half size
// to decrease latency of shifting elements.
this._elements = this._elements.slice(this._offset);
this._offset = 0;
return first;
}
front() {
return this.size() > 0 ? this._elements[this._offset] : null;
}
back() {
return this.size() > 0
? this._elements[this._elements.length - 1]
: null;
}
size() {
return this._elements.length - this._offset;
}
isEmpty() {
return this.size() === 0;
}
clear() {
this._elements = [];
this._offset = 0;
}
}
JavaScript
복사
그런데 메모리 초과가 났다.
큐 구현할 때 먼저 하려고 했던 연결리스트를 써서 메모리를 적게 들여야 된다. 한번에 맞추면 편하긴 한데 틀린 길만 다 찾아본 덕분에 모든 걸 다 겪으면서 성장하게 되었다.
배열 이용으로 시간 초과가 난 후 큐 구현을 뒤적거리다가 Single Linked List를 Queue라는 이름으로 클래스로 구현해두었던데 결론적으로 Queue보다 Single Linked List를 떠올리는 게 더 필요하다.
소스코드
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
add(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
}
this.tail = newNode;
this._size++;
return newNode;
}
getHead() {
return this.head.value;
}
removeHead() {
this.head = this.head.next;
this.head.prev = null;
this._size--;
}
getSize() {
return this._size;
}
}
function solution(i) {
let nums = i.toString().trim().split("\n");
// console.log(cards);
const cards = new LinkedList();
for (let i = 1; i <= nums; i++) {
cards.add(i);
}
let q = new LinkedList(cards);
while (cards.getSize() !== 1) {
cards.removeHead();
cards.add(cards.getHead());
cards.removeHead();
}
console.log(cards.getHead());
return;
}
test("solution", () => {
expect(solution("6")).toBe("4");
});
JavaScript
복사
