[JS] 프린터

큐에 관한 문제입니다.

저만 그런지 모르겠는데 이 문제 처음 읽으면 최우선순위 작업물 프린트하고 그 순서대로 나올 것 같지 않나요?

뒤에 설명하겠지만, 팁은 우선순위별로 계속 갱신시켜줘야합니다.

다들 푸셨나요? 같이 한번 살펴봐요!

---

문제 요약

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

 

priorities	location	return
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

 

문제 해석

전 처음에 그냥 priorities 배열에서 cursor를 1씩이동하는 루프를 썼었는데요.

이러면 최우선순위 값을 매번 splice나 slice 등을 이용해서 조정해줘야합니다. 약간 비효율적입니다.

 

이번엔 큐를 한번 이용해보겠습니다.

• prioirities의 모든 요소를 큐에 enqueue한다.
• 큐에서 최댓값과 dequeue한 값을 비교한다.
  • 같다면, 타깃 문서의 순서가 0인지(지금 대기순서가 맨 앞인지) 확인한다. (아니라면 계속 진행, 같다면 break)
  • 다르다면 그 값을 enqueue하고 대기순서를 적절히 조정한다.

이런 식으로 하면 몇 번째로 나오는지 알 수 있겠네요.

최댓값과 dequeue 값이 같다면 큐 안에서 최우선 작업물이 대기번호 0이라는 의미니 그대로 dequeue해주고 갯수를 세주면 되겠네요.

 

정답 코드

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front++];
        return val;
    }
    
    getMax() {
        return Math.max(...this.queue.slice(this.front));
    }
    
    size() {
        return this.rear - this.front;
    }
}

function solution(priorities, location) {
    const queue = new Queue();
    let count = 0;
    let order = location;
    priorities.forEach((v) => queue.enqueue(v));
    
    while (true) {
        const max = queue.getMax();
        const value = queue.dequeue();
        if (value === max) {
            count++;
            if (order === 0) break;
        } else {
            queue.enqueue(value);
        }
        order = order === 0 ? queue.size() - 1 : order - 1;
    }
    return count;
}

 

다른 자료 구조는 몰라도 큐는 진짜 자주쓰이더라구요.

몇 번 문제 풀다보면 그냥 외워져서 참 편합니다.

front, rear를 적절하게 조절하면 크기가 고정된 큐나 링버퍼 형식으로도 만들 수 있어요.

문제에 필요한 함수들을 적절하게 커스텀해서 쓰시면 인생이 편해집니다.

 

그럼 이만!