[JavaScript] Queue 구현 & 시간 복잡도 (백준 #18258번)

계기

스터디에서 코드리뷰 할 당시 팀원 모두가 왜 Queue를 이용했을 때 시간초과 결과가 나오는지에 대해 이유를 파악하지 못하고 있었고, 그 이해를 돕고자 포스팅하게 되었습니다.

 

문제

https://www.acmicpc.net/problem/18258

18258번: 큐 2

 

먼저 18258번 문제는 Queue를 활용하여 풀이하는 문제이다. 처음 Queue를 설계할 때 아래 코드와 같이 this.queueArray = [];를 두고 진행하려 하였으나 결과는 계속 시간 초과로 나왔다. 

 

시간 초과 코드

VSCode에서 컴파일 했을 때 출력 값은 맞게 나왔지만 결과가 시간 초과로 나오는데 있어서 시간 복잡도와 연관이 있다고 생각하게 되었다.

const fs = require('fs');
let input = fs.readFileSync(__dirname + '/input.txt').toString().trim().split('\n');

let lastData = '';

class Queue { 
    constructor() { 
        this.queueArray = [];
        this.queueLength = 0;
    }
    enqueue(data) { 
        this.queueArray.push(data);
        lastData = data;
        this.queueLength++;
    }//enqueue
    dequeue() { 
        let deleteData = this.queueArray.shift();
        this.queueLength--;
        return deleteData;
    }
    peek() { 
        return this.queueArray[0];
    }
    size() { 
        return this.queueLength;
    }
}//Queue

const sampleQueue = new Queue;
let result = '';

let i = 1;
while (i <= input[0]) { 
    let inputData = [];
    inputData = input[i].split(' ');

    switch ( inputData[0] ) { 
        case 'push':
            sampleQueue.enqueue(inputData[1]);
            break;
        case 'pop':
            result += ( sampleQueue.size() > 0 ? sampleQueue.dequeue() : -1) + "\n";
            break;
        case 'size':
            result += sampleQueue.size() + "\n";
            break;
        case 'empty':
            result += ( sampleQueue.size() == 0 ? 1 : 0) + "\n";
            break;
        case 'front':
            result += ( sampleQueue.size() == 0 ? -1 : sampleQueue.peek() ) + "\n";
            break;
        case 'back':
            result += ( sampleQueue.size() > 0 ? lastData : -1) + "\n";
            break;
    }
    i++;
}// while 반복문

console.log(result);

따라서 어떤 부분에서 시간 초과가 되는 건지 생각해보다가 문득 Queue를 Array가 아닌 Linked list 알고리즘을 활용하여 Queue를 구현해보자라고 생각하였다.

 

그 이후 코드

그 후 Array 부분을 Linked list로 구현하였고 해당 코드는 아래와 같다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');

class Node { 
    constructor(data) { 
        this.data = data;
        this.next = null;
    }//constructor
}//Node

let lastData = '';

class Queue { 
    constructor() { 
        this.first = null;
        this.last = null;
        this.size = 0;
    }//constructor

    enqueue(data) { 
        const newNode = new Node(data);

        if (this.first) {
            this.last.next = newNode;
            this.last = newNode;
        } else { 
            this.first = newNode;
            this.last = newNode;
        }
        this.size++;
        lastData = data;
    }//enqueue
    
    dequeue() { 
        const deleteData = this.first;
        this.first = this.first.next;
        this.size--;

        return deleteData.data;
    }//dequeue
    
    peek() {
        return this.first.data;
    }//peek
    
    count() { 
        return this.size;
    }//count
}//Queue

let result = ''; // 출력값 
const queue = new Queue();

let i = 1;
while (i <= input[0]) {
    let inputData = [];
    inputData = input[i].split(' ');

    switch (inputData[0]) {
        case 'push':
            queue.enqueue(inputData[1]);
            console.log(queue)
            break;
        case 'pop':
            result += ( queue.count() > 0 ? queue.dequeue() : -1 ) + "\n" ;
            break;
        case 'size':
            result += queue.count() + "\n";
            break;
        case 'empty':
            result += ( queue.count() == 0 ? 1 : 0) + "\n";
            break;
        case 'front':
            result += ( queue.count() == 0 ? -1 : queue.peek() ) + "\n";
            break;
        case 'back':
            result += (queue.count() > 0 ? lastData : -1) + "\n";
            break;
    }
    i++;
}// while 반복문

console.log(result);

코드 실행 결과 맞았습니다!!로 결과가 나왔다. 이로써 배열에 쓰이는 함수들이 시간초과 결과와 관련이 있다고 생각하고 이를 통해 알게된 내용을 정리하고자 한다.

 

🪐 Array, Linked list 란?

✔️ Array

• 배열은 정적(static)인 자료구조이다. 즉, 배열을 만들기 위해서 미리 크기를 정해놔야 하기 때문이다.
• 크기를 정해 놓으면 크기 수정이 불가하고 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있다.
• 하지만 연속된 메모리 주소를 할당받기 때문에 데이터가 인덱스를 가지게 되어 임의 접근(random access)이 가능해진다.

✔️ Linked list

• 연결리스트는 동적(dynamic)인 자료구조이다. 배열과 다르게 연결리스트는 크기를 미리 정할 필요가 없기 때문이다. 즉, 배열처럼 메모리 주소를 할당받는 것이 아니다.
• 연결리스트는 노드(Node)가 존재하는데 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소를 가지고 있다.
• 이 장점은 크기의 제한이 걸리지 않는다는 점이되고 이 때문에 데이터 추가, 삭제가 자유로워진다.
• 하지만 연결리스트는 배열처럼 연속적으로 메모리 주소를 할당받지 않기 때문에 데이터를 탐색하는 방식은 순차 방식(sequential access) 방식을 사용한다.

🕰️  Array, Linked list의 시간 복잡도

✔️ Array

https://sootech-story.tistory.com/entry/2%EC%A3%BC%EC%B0%A8-Stack-Queue-Linked-list

2주차 (Stack / Queue / Linked-list)

내가 포스팅했던 Stack과 Queue을 배열구조로 구현한 예시가 있다. 

Stack의 경우 push, pop를 사용하고, Queue의 경우 push, shift를 활용하였다.

• 배열의 메소드 중 push, pop 은 시간 복잡도 O(1)이다. 배열은 인덱스를 가지는데 첫 시작은 0, 끝 인덱스는 배열의 길이 -1이다. push, pop은 배열의 맨 끝 요소를 추가 및 삭제하는 것이기에 인덱스 하나만 지정해주거나 삭제하면 되기 때문에 시간 복잡도가 O(1)이 된다.
• 배열의 메소드 중 shift, unshift의 시간 복잡도는 O(n)이 된다. 앞에서 push, pop과는 달리 앞에서 요소(값)을 추가하고 삭제하기에 배열의 모든 인덱스에 영향을 끼치기 때문에 시간 복잡도가 O(n)이 된다. 따라서 내가 Queue를 배열로 코드를 설계했을 때 시간초과 결과가 나왔던 이유였다.
  • 쉽게 이해하기 위해 코드로 예를 들어보겠다.

// 기존 배열
const tempArray = [ 1, 2, 3, 4, 5 ];
//   현재 배열 인덱스 값 0  1  2  3  4

//위의 배열 앞 부분에 값 0을 추가
tempArray.unshift(0); // [ 0, 1, 2, 3, 4, 5 ]
//             배열 인덱스 값 0  1  2  3  4  5

//배열 앞 부분에 추가했던 0을 제거
tempArray.shift(0); // [ 1, 2, 3, 4, 5 ]
//           배열 인덱스 값 0  1  2  3  4

위 코드를 보면 unshift와 shift 메서드를 실행하면 해당 값들의 인덱스들이 전부 다 변경되는 것을 볼 수 있다. 

 

더 나아가 다른 메서드들의 시간 복잡도를 알아보자.

• concat, slice, splice : O(N) 
  • 배열을 이어주고, 자르고, 값을 추가하면 인덱스를 조정해줘야하므로 O(N)으로 생각하면 편하다.
• forEach, map, filter, reduce : O(N)
  • 배열의 메서드도 결국 배열의 길이만큼 배열을 순회해야하므로 O(N)으로 생각하면 된다.

✔️ linked list

• 데이터 탐색시 순차 접근 방식을 사용하기 때문에 어떤 한 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 한다. 따라서 시간 복잡도는 O(n)이다.
• 데이터 추가시 데이터 추가하는 행위 자체의 시간 복잡도는 O(1)이다. 따라서 추가하려는 데이터의 위치가 맨 앞이라면, O(1)의 시간 복잡도를 가진다. 하지만 추가하려는 데이터의 위치가 맨 앞 그 후라면, 순차적으로 탐색하면서 해당 위치까지 가야하기 때문에 발생하는 시간 복잡도가 O(n)이라고 볼 수 있다.
• 데이터 삭제시 맨 앞의 데이터를 삭제하는 것이라면 시간 복잡도는 O(1)이다. 하지만 데이터 추가할 때와 마찬가지로 맨 앞 그 이후라면 O(n)의 시간 복잡도를 갖는다.

 

📍 결론

N이 1,000 이하라면 shift를 사용해도 큰 영향력이 있지는 않은 것 같다. 따라서 Queue를 사용할 경우가 생기면 잘 판단하고 자료구조를 선택해야 한다.

 

그리고 Linked list는 노드가 있기 때문에 값의 추가, 삭제로부터 자유로워질 수 있지만 탐색이 느려진다.

Array는 연속적으로 메모리를 할당받아 데이터를 저장하기 때문에 탐색은 굉장히 빠르지만 값을 추가하거나 삭제할 때 자유로울 수 없는 특징을 알고 알고리즘과 자료구조를 설계해야 한다.