기차 티켓 대기열은 어떤 구조일까(feat.Queue)
24년 추석, 용산으로 돌아오기 위해
기차 티켓 예매를 계-속 시도했는데요.(실패하고 버스를 타고 왔습니다.. 티켓팅 힘들더라고요)
기차 티켓 예매를 위한 대기열은 어떻게 구성이 되었을지와
대기열과 비슷한 구조를 자바스크립트로 구현하면 어떨까라는
생각이 문득 들어 포스팅하게 되었습니다.
먼저 진입한 사람이 티켓 화면에 빨리 진입할 수 있다. (FIFO)
대기열을 분석해 보면 대기열 화면의 로딩이나, 순위가 빠른 사람이
먼저 예매 화면으로 접근할 수 있는 것은 모두 알고 계실 거예요.
자료 구조로 비교하자면 Queue가 사용되었겠다 싶었습니다.
Queue는 FIFO(First In, First Out) 방식으로 동작하며
먼저 들어온 요청이 먼저 처리된다는 의미를 지니고 있으니까요.
대기열에 먼저 진입하는 것을 Enqueue로,
진입한 유저를 예매 화면으로 이동시켜 주는 부분을 Dequeue라고 볼 수 있겠네요.
JS로 만들어본 간단한 Queue
// 티켓 예매 대기열 구현
function testQueue() {
const queue = {
elements: [],
// 대기열에 입장
enqueue: function(element) {
this.elements.push(element);
},
// 대기열에서 퇴장(= 예매 화면으로 이동 등)
dequeue: function() {
return this.elements.shift();
},
// 현재 입장 순번 표기
front: function() {
if (this.isEmpty()) {
return "this queue is empty!!";
}
return this.elements[0];
},
// 빈 대기열인지의 유무
isEmpty: function() {
return this.elements.length === 0;
},
// 총 예매 인원 등을 의미
size: function() {
return this.elements.length;
},
show: function() {
console.log(this.elements.toString());
}
};
return queue;
}
const queue = testQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("first element:", queue.front()); // 1
queue.show(); // 1,2,3
console.log("eliminate element:", queue.dequeue()); // 1
queue.show(); // 2,3
console.log("size of queue:", queue.size()); // 2
동작은 잘 하지만 문제가 있었습니다.
친구들과의 선착순 내기 등의 기능에는 사용이 가능했지만
코레일처럼 수십 수백만명의 동시 접속자를 고려했을 때의
상황을 고려하지 않았는데요.
대규모 데이터를 처리할 때, JavaScript의 배열 메서드인 push()와
shift()를 사용할 경우 성능 문제가 발생할 수 있다는 점을 알게 되었습니다.
특히 shift()는 배열의 첫 번째 요소를 제거할 때 배열의 모든 요소를
한 칸씩 이동시켜야 하므로 O(N)의 시간 복잡도를 가지게 되어 개선이 필요했는데요.
GPT님은 효율성을 위해 다른 자료구조를 사용하는 것을 추천했습니다.
Linked List를 사용한 대기열 구현
// Linked List node 정의
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Linked List Queue 구현
class LinkedListQueue {
constructor() {
this.frontNode = null;
this.rearNode = null;
this.size = 0;
}
// 대기열에 입장
enqueue(element) {
const newNode = new Node(element);
if (this.isEmpty()) {
this.frontNode = newNode;
this.rearNode = newNode;
} else {
this.rearNode.next = newNode;
this.rearNode = newNode;
}
this.size++;
}
// 대기열에서 퇴장(= 예매 화면으로 이동 등)
dequeue() {
if (this.isEmpty()) {
return "this queue is empty!!";
}
const removedNode = this.frontNode;
this.frontNode = this.frontNode.next;
this.size--;
return removedNode.data;
}
// 현재 입장 순번 표기
front() {
if (this.isEmpty()) {
return "this queue is empty!!";
}
return this.frontNode.data;
}
// 빈 대기열인지의 유무
isEmpty() {
return this.size === 0;
}
// 총 예매 인원 등을 의미
getSize() {
return this.size;
}
// 대기열 요소 출력
show() {
let current = this.frontNode;
const elements = [];
while (current) {
elements.push(current.data);
current = current.next;
}
console.log(elements.toString());
}
}
// 사용 예시
const queue = new LinkedListQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log("first element:", queue.front()); // 1
queue.show(); // 1,2,3
console.log("eliminate element:", queue.dequeue()); // 1
queue.show(); // 2,3
console.log("size of queue:", queue.getSize()); // 2
Linked List를 사용했을 때 3가지 장점이 있었습니다.
1. 동적 메모리 할당으로 모든 공간을 사용, 요소가 삭제될 때 메모리가 즉시 해제된다.
2. 메모리 할당이 동적이므로, 메모리 사용이 효율적이다.
큐의 크기에 따라 자동으로 조정되며, 성능이 상대적으로 일관적이라는 말이다.
2. enqueue와 dequeue 모두 O(1)로 유지. 노드를 추가하거나 제거할 때는 참조를 업데이트하는 것만 필요하다.
구현을 마치며
사실, 알고리즘을 습관처럼 1문제씩 항상 풀어오고 있지만 실생활에 자료구조를 활용한
개발이 가능한지에 대해 항상 의문을 가져오던 차, 추석 기차 티켓 예매를 경험하며
자료구조를 통한 개발의 필요성에 대해 깨닫게 되었습니다.
Linked List도 단지 배열과의 차이가 무엇인지 정도만 알고 쉬운 난이도의
알고리즘 문제를 해결할 때만 사용해 봤는데요.
실생활에 적용할 수 있다는 부분에서 왜 자료구조 공부를 해야 하는지
이유를 알게 되었습니다.