YLog

📝 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42587

목표: 주어진 프로세스 실행 대기 큐에서 특정 프로세스가 실행되는 순서를 알아내는 것이 목표. 이 때 주어진 우선순위에 따라 높은 우선순위의 프로세스를 먼저 실행해야한다.

핵심 조건:

• 큐에서 프로세스를 실행시키는 순서는 다음과 같은 규칙에 따라 진행된다

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

• 주어지는 입력은 큐의 프로세스들의 실행 우선순위를 나타내는 배열, 확인하고자 하는 프로세스의 위치 인덱스
• priorities 의 길이는 1 이상 100 이하 (최대 N=100)
• priorities 의 원소는 1 이상 9 이하의 정수 (우선순위는 1~9의 범위)
• location 은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하

🔍 풀이 과정 (나만의 풀이 전략)

이 문제의 핵심은 큐에서 우선순위가 높은 프로세스가 뒤에 있다면, 현재 꺼낸 프로세스를 맨 뒤로 보낸다는 조건을 시뮬레이션 해야하는 것이다.

그렇다면 꺼낸 프로세스의 우선순위가 현재 큐에서 가장 큰 우선순위인지를 확인하기 위해

프로세스를 꺼낼 때 마다 매번 큐의 남은 우선순위를 체크하기

그러면 dequeue를 할 때마다 큐를 순회하면서 우선순위를 체크해야한다. 시간 복잡도를 우선 고려해보자면, 최악의 경우에 주어진 location이 큐의 맨 뒤 프로세스라면 최대 N번 프로세스를 실행해야 한다. 이때 이 프로세스를 실행(dequeue) 할 때 마다 큐의 남은 우선순위를 체크하기 위해 순회를 해야하므로 N * N회 연산을 해야하므로, 시간 복잡도는 O(N^2)이 된다.

이 때 주어진 priorities 의 크기가 최대 100 이므로 N = 100 일 때 최대 연산횟수는 10,000회가 된다. 이 정도의 규모라면 시간 초과에서는 문제가 생기지 않을 것이다.

데이터 구조 설계

이 문제에서는 프로세스들을 꺼내고 다시 맨 뒤로 보내는 상황이 존재하므로, 초기 큐의 순서가 뒤바뀔 수 있기 때문에, 목표로 하는 특정 위치의 프로세스를 추적하기 위해 큐에 삽입하는 데이터 구조를 { index, priority } 객체 형태로 저장하였다.

    const queue = new Queue();
    priorities.forEach((priority, index) => {
        queue.enqueue({index: index, priority: priority});
    });

핵심 로직

    while (queue.size() > 0) {
        let isPass = false;
        const item = queue.dequeue(); // {0, 2}
        for (let i = queue.front; i < queue.rear; i++) {
            if (item.priority < queue.storage[i].priority) {
                queue.enqueue(item);
                isPass = true;
                break;
            }
        }
        if (!isPass) answer++
        if (!isPass && item.index === location) break;

    }

큐에서 front에 있는 항목을 하나 dequeue한다. 그리고 남은 큐를 순회하면서 dequeue한 프로세스의 우선순위보다 큐에 더 우선순위가 높은 항목이 하나라도 존재한다면, 해당 프로세스를 euqueue 하여 맨 뒤로 보낸다. 방금 꺼낸 프로세스를 실행하지 않고 다시 큐에 넣었다는 것을 기억하기 위해 isPass 플래그를 true로 변경하고, 순회를 즉시 탈출한다.

그리고 만약에 isPass가 false라면 즉, 꺼낸 프로세스를 다시 큐에 넣지 않고 실행했다면, 실행 횟수인 answer 를 1 증가 시킨다.

그리고 만약 이 실행한 프로세스의 원래 item.index가 location과 동일하다면 while문을 종료하고 누적된 answer 를 반환한다.

🛠️ 트러블슈팅

JavaScript 배열 shift()의 성능 이슈를 고려해 큐(Queue) 직접 구현

처음에는 배열을 이용해 JS의 Array 내장 메서드인 shift(), push()를 통해 구현하는 것을 생각했다. 하지만 자바스크립트의 shift() 메서드는 배열의 첫 요소를 추출한 후 남은 모든 요소의 인덱스 재정렬이 포함되기 때문에 O(N)

이번 문제에서 큐의 요소가 빠졌다가 다시 뒤로 넘겨지는 연산이 빈번히 발생한다. 비록 주어진 N의 크기가 최대 100이기 때문에 위 방법으로 구현하여도 이번 문제에서는 성능 문제가 발생하지 않을 수도 있지만, N의 크기가 커질 경우 시간 초과 문제가 생길수도 있을것이다.

따라서 직접 큐를 클래스로 구현하여, 삽입과 삭제 연산의 비용을 O(1)이 되도록 하여 효율성을 극대화하였다.

매번 큐를 전체 순회해야 하는 비효율성 개선 고민

이번 문제에서는 큐에서 dequeue할 때 마다 for문으로 우선순위를 순회하면서 체크하는 방식을 택했는데 이 방식 외에 더 효율적인 방법이 또 있을지 문제를 해결하고 알아보았다.

💻 코드 (Code)

class Queue {
    constructor() {
        this.storage = {};
        this.front = 0;
        this.rear = 0;
    }
    
    size() {
        return this.rear - this.front;
    }
    
    enqueue(value) {
        this.storage[this.rear] = value;
        this.rear += 1;
    }
    
    dequeue() {
        if (this.size() === 0) return null;
        const temp = this.storage[this.front];
        delete this.storage[this.front];
        this.front += 1;
        return temp;

    }
    
}

function solution(priorities, location) {
    var answer = 0;
    const queue = new Queue();
    priorities.forEach((priority, index) => {
        queue.enqueue({index: index, priority: priority});
    });

    while (queue.size() > 0) {
        let isPass = false;
        const item = queue.dequeue(); // {0, 2}
        for (let i = queue.front; i < queue.rear; i++) {
            if (item.priority < queue.storage[i].priority) {
                queue.enqueue(item);
                isPass = true;
                break;
            }
        }
        if (!isPass) answer++
        if (!isPass && item.index === location) break;

    }
    
    
    return answer;
}

최적화된 코드

class Queue {
    constructor() {
        this.storage = {};
        this.front = 0;
        this.rear = 0;
    }
    
    size() {
        return this.rear - this.front;
    }
    
    enqueue(value) {
        this.storage[this.rear] = value;
        this.rear += 1;
    }
    
    dequeue() {
        if (this.size() === 0) return null;
        const temp = this.storage[this.front];
        delete this.storage[this.front];
        this.front += 1;
        return temp;

    }
    
}

function solution(priorities, location) {
    var answer = 0;
    const queue = new Queue();
    priorities.forEach((priority, index) => {
        queue.enqueue({index: index, priority: priority});
    });
    
    // 이 배열의 맨 앞은 항상 '현재 큐에 남아있는 최고 우선순위'를 의미
    const sortedQueue = [...priorities].sort((a, b) => b - a); 
    let maxIndex = 0; // // 현재 가장 높은 우선순위를 가리키는 포인터

    while (queue.size() > 0) {
        const item = queue.dequeue();
        // // 현재 꺼낸 아이템의 우선순위가 남아있는 최고 우선순위보다 낮다면
        if (item.priority < sortedQueue[maxIndex]) {
            queue.enqueue(item); // 맨 뒤로 보내기
        } else {
		        // 현재 꺼낸 아이템이 최고 우선순위라면 실행
            answer++;
            
            maxIndex++;
            
            // 방금 실행한 프로세스가 우리가 찾던 목표 위치라면 종료
            if (item.index === location) {
                break;
            }
        }

    }
    
    
    return answer;
}

기존 방식은 큐에서 프로세스를 하나 꺼낼 때 마다 뒤에 더 큰 값이 있는지 확인하기 위해 큐 내부를 순회하므로 O(N^2)

이 방식은 이미 내림차순으로 정렬한 sortedQueue 배열을 생성하는데 O(N log N)이 걸리고 다음으로 while 루프를 돌면서 sortedQueue의 maxIndex 위치의 값과 비교만 하면 되므로, O(1)의 시간이 소요된다.

따라서 while 문에서 원소들이 큐를 나갔다 들어왔다만 수행할 뿐 내부에서 전체를 다시 순회하는 연산이 사라지므로, 큐 연산 자체는 O(N)이 된다.

전체 시간 복잡도는 O(N) + O(N log N)으로 최적화 된다.

❓ 꼬리 질문 및 복습 (Self-Q&A)

꼬리질문

Q1. 최적화 풀이에서 정렬 배열(sortedQueue)을 썼는데, 만약 우선순위의 범위가 1 ~ 9가 아니라 대단히 크고 데이터 수가 훨씬 많다면 어떤 방식이 더 유리했을까?

현재는 내림차순 정렬O(N log N)을 이용해 최댓값을 추적했다. 만약 실시간으로 데이터가 추가 및 삭제되거나 데이터 규모가 매우 크다면, 현재 최댓값을 항상 O(1) 혹은 O(log N)으로 유지해 주는 최대 힙(Max Heap) 기반의 우선순위 큐(Priority Queue) 자료구조를 직접 구현해 적용하는 것이 정석적인 확장 방향이다.

💬 마무리하며

사실 이번 문제에서는 큐를 직접 구현하지 않고 배열의 메서드를 이용한다면 더 쉽게 풀이할 수 있던 문제였습니다. 해결하면서 큐를 다시 복습하면서 shift() 메서드가 가지는 성능 면에서의 우려점을 고려해서 해본 풀이였습니다. 그래도 다음에 이 경험이 도움이 되지 않을까? 생각이 듭니다.

오늘도 파이팅입니다!