[Javascript] 코테용 큐 구현

💡 하루 한문제씩 풀이할 땐 "풀 수 있는 문제" 위주로 풀었습니다. 그러다 보니 실력이 좋아진다기보단 익숙해진다 정도의 느낌 밖에 없었습니다.

코 앞에 코딩 테스트

그렇게 지내다 갑작스레 코테를 치게 되었습니다. 눈앞에 코테가 있다보니 모르는 문제들을 꼭 풀어야 하는 상황이더라구요😭 그래서 못 푸는 문제들을 손대기 시작했습니다.

처음엔 막막했는데, 막상 차근차근 배워가니 의외로 재밌고 아는 문제를 풀 때 보다 기분도 좋아지는군요. 🤣

이맛에 PS를 하는건가 다들 ㅎㅎ

큐 구현 - 그래서 큐는 어떻게 구현하는데?

Javascript 기본 라이브러리에는 큐가 없습니다. 다른 언어를 선택한다면 쉽게 풀이할 수 있지만 JS를 선택한 이상 큐를 직접 구현해야합니다.

니가 택한 JS다... 악깡버해라...😭

큐를 직접 구현하지 않고, Array 내장 함수인 push, shift를 사용하면 동작은 됩니다. 하지만 shift 함수가 0번 원소를 삭제하고 남은 원소들을 앞으로 이동해주는 방식이라 O(n)의 복잡도를 가집니다. 이럴 경우 시간 복잡도가 중요한 문제에서 불리하게 됩니다.

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++;
    return value;
  }

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

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

그래서 Array를 이용해 위처럼 빠르게 구현해서 사용하면 됩니다. (더 필요한 기능은 직접 만들어서 사용하면 됩니다.)

자료구조를 처음! 접하시면 위 코드가 굉장히 복잡하게 느껴집니다. 저도 그랬으니까요. 하지만 "정복해야겠다." 라는 생각을 가지고 아래와 같이 하시면 자연스레 익숙해집니다.

1) 큐 개념을 이해한다. (대기줄과 같은 자료구조)
2) `무지성`으로 일단 따라친다.
3) 차근차근 개념과 코드를 연계해서 생각해본다.
4) 백지상태로 직접 코드를 쳐본다. 
	기억 안나면 살짝씩 보면서 따라친다. 
    몇 번 지웠다 썼다 하면 안보고 완벽하게 따라쳐진다.
5) 백준 단계별에서 `큐` 문제를 푼다.

끝으로

제가 지금 5번까지 마무리한 상태인데요, 언제 이 모든걸 다 배우나... 싶었지만 막상 "해야 하는 상황"에 닥치게 되니 몇시간 안되서 위 과정을 마무리하게 되었습니다.

혹시나 자료구조 공부로 골치아프신분이 있으시면 위 과정대로 해보시면 생각보다 간단하게 머릿속에 들어오는걸 경험하실 수 있을겁니다.

다같이 화이팅~!