<div id="readability-page-1" class="page"><div><ol>
<li>스택/큐란?</li>
</ol>
<ul>
<li>스택<br>
LIFO(Last In First Out)<br>
실 사용 예시 : 스택메모리, js 콜스택</li>
<li>큐<br>
FIFO(First In First Out)<br>
심화 : 원형 큐</li>
</ul>
<ol start="3">
<li>코테<br>
핵심 키워드 : 차례대로, 순서대로, 하나하나<pre><code>대표문제 
- 올바른 괄호(쉬움)
- 프린터(프로그래머스 고득점 kit lv 2)</code></pre><img src="https://velog.velcdn.com/images/2taesung/post/c25afc66-b4b2-4d47-9dfd-afb330192d10/image.png"></li>
</ol>
<pre><code>class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

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

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

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

  size() {
    return this.rear - this.front;
  }
}

function solution(priorities, location) {
  const queue = new Queue();
  for (let i = 0; i &lt; priorities.length; i += 1) {
    queue.enqueue([priorities[i], i]);
  }

  priorities.sort((a, b) =&gt; b - a);

  let count = 0;
  while (true) {
    const currentValue = queue.peek();
    if (currentValue[0] &lt; priorities[count]) {
      queue.enqueue(queue.dequeue());
    } else {
      const value = queue.dequeue();
      count += 1;
      if (location === value[1]) {
        return count;
      }
    }
  }
}

console.log(solution([1, 1, 9, 1, 1, 1], 1))</code></pre>
<p>=&gt; 스택/큐 코테에서 한가지 이슈가 있는데 큐를 구현하는 shift() 함수가 O(n)의 선형 시간이 걸린다는 점이다.<br>
=&gt; O(n)은 반복문과 함께 O(n^2)로 쉽게 진화할 여지가 있어 조심해서 써야한다.<br>
=&gt; 해결책은 위와 같이 list, likend list로 Queue를 직접 구현해 사용한다. (O(1) 상수 시간이 걸림)</p>
<p>심화 문제 : 다리를 지나는 트럭(프로그래머스 고득점 kit lv 2)</p>
<p><img src="https://velog.velcdn.com/images/2taesung/post/cf92dd94-19b2-4c06-8e39-3510196ace9b/image.jpg"></p></div></div>

2taesung.log

Taesung Lee

스택/큐란?
스택
  LIFO(Last In First Out)
  실 사용 예시 : 스택메모리, js 콜스택
큐
  FIFO(First In First Out)
  심화 : 원형 큐
코테
 핵심 키워드 : 차례대로, 순서대로, 하나하나
 대표문제 
올바른 괄호(쉬움)
프린터(프로그래머스 고득점 kit lv 2)
class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}
function solution(priorities, location) {
  const queue = new Queue();
  for (let i = 0; i < priorities.length; i += 1) {
    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 += 1;
      if (location === value[1]) {
        return count;
      }
    }
  }
}
console.log(solution([1, 1, 9, 1, 1, 1], 1))
=> 스택/큐 코테에서 한가지 이슈가 있는데 큐를 구현하는 shift() 함수가 O(n)의 선형 시간이 걸린다는 점이다.
=> O(n)은 반복문과 함께 O(n^2)로 쉽게 진화할 여지가 있어 조심해서 써야한다.
=> 해결책은 위와 같이 list, likend list로 Queue를 직접 구현해 사용한다. (O(1) 상수 시간이 걸림)
심화 문제 : 다리를 지나는 트럭(프로그래머스 고득점 kit lv 2)

스택/큐

댓글