[파이썬/알고리즘] 프로그래머스 - 프로세스 (큐)

[문제]

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

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

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

 

[풀이]

def solution(priorities, location):
    queue = [(index, p) for index, p in enumerate(priorities)]
    answer = 0

    while True:
        current = queue.pop(0)
        if any(current[1] < q[1] for q in queue):
            queue.append(current)
        else:
            answer += 1
            if current[0] == location:
                return answer

 

예시  priorities = [4,5,6], location = 1

 

queue = [(index, p) for index, p in enumerate(priorities)]

enumerate 함수를 이용하여 priorities에 인덱스를 부여한다.

만약 priorities = [4,5,6] 이였을 때 인덱스를 부여하면 파이썬은 0부터 시작하므로 [(0,4), (1,5), (2,6)] 이 된다.

처음에 있는 0,1,2는 순서대로 인덱스이고 4,5,6은 원래 값이다.

 

answer = 0

정답을 0으로 초기화 해준다.

 

while True:
      current = queue.pop(0)

조건을 반복할 때까지 무한 반복하는 것이다.

여기서 current는 큐에서 첫 번째에 있는 원소를 꺼내고 여기서 기억해야 할 것은 추후에 설명하겠지만 큐는 FIFO 구조로 먼저 들어온 것이 먼저 나가게 된다.

 

위 예시에서 처음 반복문을 들어오면 (0,4)가 currnet값으로 할당된다.

if any(current[1] < q[1] for q in queue):
       queue.append(current)

any라는 함수는 조건을 만족하는 것이 하나라도 있을 경우 True를 반환한다. 

 

current[1]은 위에서 들었던 예시 (0,4)에서 첫 번째 원소 즉 4를 의미한다. 이 4와 q[1]인 5와 6을 각각 비교하게 된다.

우선순위가 더 큰 5가 있으므로 현재 (0,4)를 다시 큐에 넣는다. 여기서 넣게 되면 맨 마지막으로 들어가게 된다.

[(1,5), (2,6), (0,4)] 가 된다. 그리고 다시 while 반복문으로 돌아가서 반복하게 된다.

 

이번엔 current에 (1,5)가 할당되고 다시 if문에서 5보다 더 큰 6이 있기 때문에 [(2,6), (1,5), (0,4)]로 바뀌고 다시 while문으로 돌아간다.

 

else:
     answer += 1
      if current[0] == location:
                return answer

[(2,6), (1,5), (0,4)] 큐는 if문에 걸리지 않으므로 else문으로 들어오게 되고 answer을 하나 더해진다.

이 answer이 1이면 처음으로 나갔다는 것이고, 2가 되면 두 번째로 나갔다는 의미가 된다.

 

그리고 여기서 만약 current[0], 즉 index가 문제에서 찾고자 하는 location과 같다면 answer을 반환하여 몇 번째로 나갔는지 알 수 있다.

 

하지만 예시에서는 location이 1 이고 제일 먼저 나간 것은 (2,6)으로 current[0]은 2이기 때문에 if문으로 들어갈 수 없다.

따라서 다시 while 반복문으로 들어가고 else문으로 들어와서 (1,5)에서 current[0]은 1이고 location도 1 이어서 if문을 만족하므로 answer 즉 2가 리턴되고 정답이 된다.