[python] 프로그래머스 스택/큐 level2 - 프로세스

 

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

프로그래머스

 

코드.

def solution(priorities, location):
    
    answer = [-1]*len(priorities)
    
    cnt = 1
    len_ = len(priorities)
    ind = 0
    while answer[location] == -1:
        
        if priorities[ind] == max(priorities):
            answer[ind] = cnt
            cnt += 1
            priorities[ind] = -1
        
        ind += 1
        ind %= len_

    
    return answer[location]

사실 이코드는 내가 짠거고,

시간복잡도가 O(n^2)으로 상당히 비효율 적이다.

 

스택/큐 문제인 만큼 해당 묘듈을 사용해서 문제를 풀어보자.

 

from collections import deque

def solution(priorities, location):
    
    queue = deque([(priority, idx) for idx, priority in enumerate(priorities)])
    process_cnt = 0
    
    while queue:
        current = queue.popleft()
        
        if any(current[0] < item[0] for item in queue):
            queue.append(current)
        else :
            process_cnt += 1
            if current[1] == location:
                return process_cnt

    return process_cnt

 

이 방법은 deque를 사용함으로

시간복잡도를 O(n)으로 줄여줘서 훨씬 효율적인 코드가 된다.