[프로그래머스] Queue에 대해 알아보자 - 프린터 문제 실습

큐에 대하여 알아보자

출처: 프로그래머스 강의, '코딩테스트 광탈 방지 A to Z Javascript'

 

큐란 먼저들어온 것이 먼저 나가는 것을 말한다.

쉬운 예를 들자면 영화관에 줄을 서면 먼저 슨 사람이 먼저 입장하고 줄에서 빠져나간다.

 

이러한 개념을 자바스크립트로 만들어 보자.

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

class Queue {
  constructor(){
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  enqueue(newValue){
    const newNode = new Node(newValue);
    if(this.head === null){
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size ++;
  }
  
  dequeue(){
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }
  
  peek(){
    return this.head.value;
  }
}

 

enqueue는 Queue에 새로운 노드를 추가,

dequeue는 head의 노드를 리턴시키고 Queue에서 제거,

peek은 현재 head값을 알려주는 메소드이다.

 

여기서 head란 Queue 스택의 가장 앞쪽의 노드를 뜻하며 tail은 가장 마지막 노드를 뜻한다.

 

 

프로그래머스의 레벨 2단계의 문제중 큐에 관련된 문제로 '프린터'가 있다.

프로그래머스 -> 코딩테스트 연습에 들어가면 해당 문제를 찾아볼 수 있다.

해당 문제에 대한 풀이 (강의에서 제시한 답안이다.)

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;
    }
    
    peek(){
        return this.head.value;
    }
}


function solution(priorities, location) {
    
    const queue = new Queue();
    for(let i = 0; i < priorities.length; i++){
        queue.enqueue([priorities[i], i]);
    }
    
    priorities.sort((a, b) => b - a);
    
    let count = 0;
    while(true){
        const currentValue = queue.peek();
        if(currentValue[0] < priorities[count]){
            queue.enqueue(queue.dequeue());
        } else {
            const value = queue.dequeue();
            count ++;
            if(location === value[1]){
                return count;
            }
        }
    }
    
    return count;
}

간단히 설명을 하자면

1. 프린터 대기목록을 받아와서 Queue스택에 저장한다. 여기서 index를 통해 답을 도출해야 하기 때문에 i값까지 저장한다.

2. priorities의 값이 클수록 중요도가 높기 때문에 sort를 이용하여 내림차순으로 정렬한다.

이 과정에서 

3. peek을 통해 head값의 currentValue를 불러온다. 여기서 currentValue[0]의 값은 중요도, currentValue[1]값은 index가 된다.

내림차순으로 정렬한 priorities는 중요도 순으로 정렬이 되어있는 상태 => priorities[count]는 중요도가 높은 것부터 시작하여 배열을 루프하게 된다.

4. 만약 현재의 value가 중요도보다 낮다면 dequeue를 통해 배열에서 제거 후 enqueue를 통해 배열 가장 마지막에 추가한다.

5. 만약 현재의 value가 중요도보다 높거나 같다면 그 값을 dequeue하여 제거 한 후 count를 늘린다. 여기서 count는 프린트 되는 순서.

6. 만약 그것이 location, 즉 문제에서 요구하는 자리의 node라면 count를 return하고 루프를 빠져 나온다.

 

마무리이이...

코딩테스트 준비를 많이 안해본 나로서 class를 선언하여 문제에서 풀어낸다는 것이 굉장히 생소했다. 다른사람들의 풀이만 봐도 이런 경우가 흔하진 않은 것 같다.

하지만 개념을 이해하고 정의 그대로 선언하여 사용한다는 것이 굉장히 유의미한 풀이였다고 생각한다.

전에 풀지 못했었던 문제였었는데 강의에서 다뤄 주셔서 좋았던 것 같다. 하지만 아직 강의에서 제시해 준 답안을 혼자 글쓴답시고 설명해보려 하니 역시나 이해가 한번에 되지 않았다. 몇번을 곱씹어 보고 나서야 글로 풀어서 겨우 쓸 수 있었다.

강의에서 만약에 못풀겠다 싶으면 며칠이고 붙잡고 있지 말고 우선 다른사람의 풀이를 보라고 하셨다. 그리고 그 풀이가 이해가 안된다면 일단 외우는 것도 방법이라고, 외워서 여러번 사용하다 보면 이해가 되는 경우가 많다고 하셨는데 이번 같은 경우도 그런 경우인듯. 계속 이해해 보려 노력하니 진짜 이해가 된 느낌이다.

 

여담으로 프로그래머스에서 유료로 제공하고 있는 '코딩테스트 광탈 방지 A to Z Javascript' 강의는 나같은 비전공자에게 도움이 많이 되는 강의인 것 같다.

우선 알고리즘, 자료구조에 대해 지식이 전무한 사람에게 정말 간단하고 컴팩트하게 개념을 알려준다.

우리는 코딩테스트라는 시험을 준비하는 것이지, 알고리즘의 전문가가 되려는 것이 아니기 때문에 이러한 강의가 굉장히 효율성 높다고 생각한다. 나같은 처지에 놓여있는 사람들에게 강추하는 바이다!