프로그래머스 - 프로세스 (스택/큐)

 

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

프로그래머스

이 문제를 처음 읽었을 때 , 문제 이해부터 필요했음

 

예를 들어 

프로세스 [A,B,C,D] 에 대응 되는 우선순위 배열인 priorities 가 [2,1,3,2] 로 주어졌을 때 

우선순위는 A=2 , B=1 ,C=3 ,D=2 로 배정됨

우선순위는 값이 클수록 순위가 높은 것

 

1. 큐의 맨 앞에서 대기중인 A를 꺼내 검사 (A의 우선순위 2)

2. A를 제외한 나머지 요소들의 우선순위를 검사하여 더 높은게 있는지 확인

3 - 더 높은게 있다면 , 다시 큐에 A를 넣고 1~2 반복 (A의 우선순위 2 보다 큰 3이 있으므로 큐에는 다시 A가 들어감)

3 - 더 높은게 없다면 , 해당 프로세스 실행 후 남은 프로세스에서 1~2 반복

 

위 과정을 반복하여 프로세스는 C, D, A, B 순으로 실행됨

from collections import deque

def solution(priorities, location):
    arr = deque(priorities)
    idxarr = deque([i for i in range(len(arr))]) //인덱스 위치 추적을 위한 인덱스 배열 생성
    answer = 1 // 해당 location의 값이 몇번째로 실행되는지
    maxnum = max(arr) 

    while arr:
        a = arr.popleft()
        b = idxarr.popleft()
        if a == maxnum and b == location: //꺼낸 값의 우선순위가 가장높고 , 현재 위치가 location 과 같다면 answer 반환
            return answer
        elif a == maxnum: //꺼낸 값의 우선순위가 가장높지만 , 현재 위치가 location이랑 다를때
            answer += 1 // 찾고있는 location의 값이 첫번째로 실행되는 게 아니기때문에 +1
            maxnum = max(arr) //우선순위가 가장 높은 값을 pop 한 뒤에 배열에서의 최댓값 재설정
        else: // 검사한 값이 우선순위가 가장높은 값이 아닐때
            arr.append(a) // arr배열에 다시 추가
            idxarr.append(b) // idxarr 배열에 인덱스 번호 다시 추가

    return answer

 

주어진 우선순위 배열을 저장하기 위한 arr 

 

할당된 location에 맞게 위치를 찾을 수 있는 방법을 찾아보다 idxarr 이라는

우선순위 배열에 매칭되는 인덱스를 추적하기위한 인덱스 배열을 생성해주었음

 

유사 문제

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐