[programmers] 프로세스 / 큐

문제

문제 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

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

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• priorities의 길이는 1 이상 100 이하입니다.
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

입출력 예prioritieslocationreturn

[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 프로세스 [A, B, C, D, E, F]가 대기 큐에 있고 중요도가 [1, 1, 9, 1, 1, 1] 이므로 [C, D, E, F, A, B] 순으로 실행됩니다. 따라서 A는 5번째로 실행됩니다.

왼 : 강사님 풀이 / 오 : 내가 최적화한 풀이

# 강사님 풀이
def solution(priorities, location):
    indexPriorityDict = dict()  # index -> 중요도
    waitQueue = list()  # 대기열
    printQueue = list()  # 프린트 된 열

    # 초기화부
    # A B C D - 0 1 2 3
    for i in range(len(priorities)):
        waitQueue.append(i)
        indexPriorityDict[i] = priorities[i]

    while True:

        index = waitQueue.pop(0)  # 대기열 꺼내기!
        priority = indexPriorityDict.pop(index)
        maxPriority = max(indexPriorityDict.values())

        if priority < maxPriority:  # 뽑은 index 우선순위가 남은 대기열보다 작을 때! -> 다시 들어가야함
            waitQueue.append(index)
            indexPriorityDict[index] = priority
        else:  # 뽑은 index가 남은 인덱스보다 크거나 같을 때 -> 나갈수 있다.
            printQueue.append(index)
            if len(waitQueue) == 1:
                printQueue.append(waitQueue.pop(0))
                break
                
    return printQueue.index(location) + 1

# 내가 최적화한 풀이
def solution(priorities, location):
    indexes=[i for i in range(len(priorities))]
    
    count = 0
    
    while len(priorities):
    
        maxpriorities = max(priorities)
        maxindex = priorities.index(maxpriorities)

        for _ in range(maxindex):
            priorities.append(priorities.pop(0))
            indexes.append(indexes.pop(0))
            
        count += 1

        priorities.pop(0)
        printidx = indexes.pop(0)

        if printidx == location:
            return count

처음엔 튜플로 (우선순위, 인덱스번호)로 묶어서 나열하고 정렬로 해결하려 했다. 하지만 우선순위가 같을 경우 인덱스 번호 순으로 정렬되어선 안되므로 튜플로 해결 불가.

인덱스 번호가 담긴 큐를 만들어 우선순위가 담긴 큐와 동일한 작업을 하는 것으로 변경. 최상위 우선순위가 pop 될  때 까지 앞 순서의 프로세스는 뒤로 append해주고, 다음 시행할 우선순위가 동일한 프로세스가 여러개일 경우, 인덱스를 추출하면 앞의 것(인덱스 숫자가 작은 것)부터 반환하므로 앞순서부터 차례대로 진행할 수 있다. 따라서 0번째 인덱스만 반복해서 pop해주면 된다. 여기서 강사님의 풀이와 차이점을 두었는데, 강사님은 모든 프로세스를 순회하여 정리한 다음 제시된 location이 위치한 순서의 index를 뽑아낸 반면, 나는 각각의 순서에서 뽑아낸 프로세스의 원래 인덱스가 location과 일치하면 뽑아낸 순서를 반환하도록 했으므로 모든 프로세스를 순회하지 않아도 되게끔 변경했다. 

 

추가로 참고할 자료

[자료구조] 스택과 큐, 데크(Stack, Queue, Deque)

프로그래머스