프로그래머스 Level 2 | 프로세스 | Python 풀이

문제 파악

문제에서 제시한 규칙대로 흐름을 구현하면 된다.

프로세스들이 우선순위를 가진 채 대기열에 존재한다.
대기열 맨 앞 프로세스가 현재 대기열 중 최댓값이 아니면 다시 큐에 넣는다.(큐의 맨 뒤로 보낸다.)
그렇지 않으면 해당 프로세스를 실행하고, 내가 궁금한 프로세스(location)가 몇 번째로 실행되는지를 구하는 문제다.

2에 다시 큐에 넣습니다. 를 큐의 맨 뒤로 보낸다를 떠올리지 못해 애를 먹었다.

핵심 아이디어

큐에 (인덱스, 우선순위) 형태로 보관한다.
우선순위가 1~9 밖에 없어서 몇개 들어있는지 미리 배열을 만들어 시간복잡도를 줄인다.
실행할 때마다 order += 1로 실행 순서를 증가시킨다.
location에 해당하는 프로세스가 실행되는 순간 order를 반환한다.

해답 및 풀이

from collections import deque

def solution(priorities,location):
    q = deque()

    for i , p in enumerate(priorities):
        q.append((i,p)) # deque([(2, 0), (1, 1), (3, 2), (2, 3)]) (값,인덱스) 형태로 deque에 추가됨

    counts = [0] * 10
    for p in priorities:
        counts[p] += 1
    #  [0,1,2,1,0,0,0,0,0,0] 우선순위 0~9이기에 각각 몇개의 프로세스들이 있는지 카운트 리스트 생성

    
    # 현재 남아있는 최댓값을 가리키는 포인터
    curr_max = 9
    while curr_max > 0 and counts[curr_max] == 0:
        curr_max -= 1

    order = 0

    while q:
        i, p = q.popleft() # 큐의 요소들을 하나씩 왼쪽부터 꺼내줄건데
        
        if p < curr_max:
            q.append((i,p)) # 큐에 맨 뒤로 보내버림
        else: # 값이 curr_max 보다 크거나 같다면

            order += 1

            counts[p] -= 1

            # i가 내가 찾는 location의 값과 일치하다면 , 그 즉시 order가 답이됨. 여기서 만약 return을 안해주면 order가 점점커져서 내가 찾는 위치의 order를 못찾음
            if i == location:
                return order
            
            # 최댓값 업데이트
            if counts[p] == 0:
                while curr_max > 0 and counts[curr_max] == 0 :
                    curr_max -= 1