[큐] 프로그래머스 Lv.2 프로세스 (문제 풀이)

🍀 배열로 Queue를 구현하여 풀기

배열로 Queue를 구현하는 방법은 앞 글에 설명해두었으니 참고하시길 바랍니다!

이 문제를 처음 봤을 때 풀지 못했고, 이선협 강사님이 Linked List 로 Queue를 구현하여 푸시길래 같이 풀어보고

다시 Array를 이용해 풀어보았습니다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  //dequeue 는 항상 값을 반환해준다는 걸 잊지 말기!
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;

    return value;
  }

  peek() {
    return this.queue[this.front];
  }
}

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) {
    for (const item of queue.queue) {
      if (item[0] < priorities[count]) {
        queue.enqueue(queue.dequeue());
      } else {
        const value = queue.dequeue();
        count++;
        if (value[1] === location) {
          return count;
        }
      }
    }
  }
}

priorities의 인덱스를 알고 있어야 하기 때문에 배열 형식으로 enqueue해주는 것을 배웠다.

Queue에는 그냥 하나의 숫자만 들어갈 수 있는 게 아니었던 것이다.

 

if(item[0] < priorities[count])에서 count 를 인덱스로 사용한 것에 놀랐다. 

하,, 열공하자

 

 

 

☘️ Linked List로  Queue를 구현하여 풀기

Queue 를 구현하는데에는 배열을 이용하는 것이 더 간편하다. 하지만 Linked List로 구현하는 방법도 알아두자!

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;
      }
    }
  }
}

배열로 푼 것과 같은 원리이다.

배열로 풀었을 땐 currentValue 변수를 사용하지 않고, for of 문을 돌렸다는 차이 뿐 코드는 동일하다.

---

🔔 질문이 있으시면 댓글에 달아주세요 :)