[스택/큐] 프로세스 - Python / Javascript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

 

[문제 간단 요약]

1. 프로세스가 아래의 규칙에 따라 작업이 수행 

• 우선 순위가 가장 높은 프로세스를 우선 실행
• 가장 높은 프로세스가 아닌 경우 대기 목록의 맨뒤에 위치

2. 특정 위치의 프로세스가 몇 번째로 실행되는지 반환

[문제 해결 방안]

1. 현재 프로세스의 위치의 인덱스를 함께  Queue에 저장

2. 큐에서 하나씩 꺼내며, 더 높은 우선순위가 있는지 확인

3. 가장 높은 우선 순위 일 경우, 카운트 증가 및 특정 위치의 프로세스인지 확인

 

[문제 해결 코드 - python]

from collections import deque
def solution(priorities, location):
    answer = 0
    sorted_priorities = sorted(priorities, reverse=True)
    q = deque()
    sq = deque(sorted_priorities)
    for i in range(len(priorities)):
        q.append([i,priorities[i]])

    while sq:
        val = sq.popleft()
        while q:
            idx, priority = q.popleft()
            if val == priority:
                answer+=1
                break
            else:
                q.append([idx, priority])
        if location == idx:
            break
    return answer

 

[문제 해결 코드 - javascript]

function solution(priorities, location) {
    let q = priorities.map((priority, idx) => ({idx, priority}));
    let answer = 0;
    
    while (q.length > 0) {
        const current = q.shift();
        if (q.some(item => item.priority > current.priority)) {
            q.push(current)
        } else {
            answer++;
            if (current.idx === location) {
                return answer
            }
            
        }
    }
}

 

코드 개선점

- deque+정렬을 통해 문제 해결 (O(N²))

- deque+heapq 를 사용하여 문제 해결도 가능 (O(N log N))

from collections import deque
import heapq

def solution(priorities, location):
    q = deque([[i,p] for i, p in enumerate(priorities)])
    max_heap = [-p for p in priorities]
    heapq.heapify(max_heap)
    answer = 0
    while q:
        idx, priority = q.popleft()
        if priority == -max_heap[0]:
            heapq.heappop(max_heap)
            answer += 1
            if idx == location:
                return answer
        else:
            q.append((idx, priority))