[큐] 프린터

Problem. 프린터

---

Link.

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

---

Approach.

자료구조 - 연결 리스트(Linked List)로 구현한 큐(Queue)

문제를 풀기 위해서 유명한 자료구조 큐(Queue)를 사용할거다. 

이때 큐는 연결 리스트(Linked List)로 구현할 것이다.

연결 리스트에서 한 노드는 값(this.value)와 다음 노드를 가르키는 포인터(this.next)로 구성되어있다.

여기서 맨 앞에 있는 노드를 head, 맨 뒤에 있는 노드를 tail이라고 일반적으로 부른다.

이러한 큐의 자료구조는 선입선출(FIFO, First In First Out)로 잘 알려져 있다.

 

연결 리스트 (linked list)

큐에 데이터 삽입하기 - 앤큐(Enqueue)

큐에 데이터를 삽입하면 뒤에서부터 하나씩 쌓이게 된다.

큐에 데이터를 삽입하는 과정 (Enqueue)

 

큐에 데이터 삭제하기 - 디큐(Dequeue)

큐에 데이터를 삭제할 때는 앞에 있는 데이터부터 하나씩 빼내게 된다.

큐에서 데이터를 삭제하는 과정 (Dequeue)

---

My Answer. 

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

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    
    enqueue(newValue) {
        const newNode = new Node(newValue)
        if (this.head === null) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
    }
    
    dequeue() {
        const value = this.head.value;
        this.head = this.head.next;
        return value;
    }
    // 현재 큐의 head 값 반환
    peek() {
        return this.head.value;
    }
}

function solution(priorities, location) {
    const queue = new Queue();
    for(let i = 0; i < priorities.length; i++) {
    	// queue에 priorities 값과 인덱스를 배열로 넣어줌
        queue.enqueue([priorities[i], i]);
    }
    // 내림차순으로 정렬
    priorities.sort((a, b) => b - a);
    
    let cnt = 0;
    
    while(true) {
        // 현재 Queue head의 value
        const currentValue = queue.peek();
        if (currentValue[0] < priorities[cnt]) {
        	// 현재 Queue head의 값이 priorities 배열에 cnt번째 값보다 작으면
            // Queue head 값을 tail로 넘김
            queue.enqueue(queue.dequeue());
        } else {
        	// 현재 Queue head의 값이 priorities 배열에 cnt번째 값보다 크거나 값으면
            // Queue head 값을 빼낸다
            let value = queue.dequeue();
            cnt++;
            // 빼낸 값이 문제에서 찾기 원하는 값이면
            // cnt 반환 및 while문 종료
            if (value[1] === location) {
                return cnt;
            }
        }
    }
}

---

References.

• 코딩테스트 광탈 방지 A to Z: JavaScript (이선협)

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)