[Python] 프로그래머스 프로세스 문제 풀이 및 정답 코드

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=python3

프로그래머스

 

문제 설명

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

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 … 과 같이 표현합니다.

문제풀이

이번 문제는 간단한 큐에 대한 문제이다. 문제를 읽어보다 보면 우선순위 큐와 조금 헷갈릴 수 있는데,

작동 방식이 완전 다르다.

(우선순위 큐는 힙 자료형을 사용하기 때문에, 가장 우선순위가 높은 프로세스를 먼저 뽑는데, 본 문제에서 사용되는 큐의 경우, 우선순위가 낮은 데이터를 다시 넣기 때문에 프로세스 추출은 같으나, 속도에서 큰 차이가 발생한다.)

 

아무튼 이번 문제의 경우 특정 프로세스가 몇 번째에 나오게 되는지 알아보기 위한 문제이다.

 

따라서, 큐를 돌면서 우선순위가 더 높은 프로세스가 존재한다면, 이를 다시 큐에 넣고 다음 프로세스를 순차적으로 추출한다.

 

여기서 location의 정보를 지니고 있어야 나중에 해당 프로세스가 나오게 되었을 때, 알 수 있으므로 처음에 전처리를 통해

큐의 원소를 (타겟 여부, 우선순위 값)으로 수정해주었다.

 

이를 기반으로 큐를 순회하면서 프로세스를 추출하고 비교해보았다.

 

정답코드로는 두가지를 두었는데, 처음에 올린 코드는 이해를 돕기 위한 주석이 달려 있는 것이며,

두번째 코드는 이를 압축한 코드이다.

정답코드

def solution(priorities, location):
    # 우리가 알고자 하는 프로세스 구분자 추가
    priorities = [(False, prior) if i != location else (True, prior) for i, prior in enumerate(priorities)]
    answer = 0
    
    while priorities:
        # 실행 대기 큐에서 대기 중인 프로세스 하나 꺼냄
        target, process = priorities.pop(0)
        
        # 대기중인 프로세스 중 우선순위가 더 높은 게 있다면, 꺼낸 것을 다시 안에 넣음
        # 그런 프로세스가 없다면, 해당 프로세스를 실행
        trigger = False
        for p in priorities:
            if process < p[1]:
                priorities.append((target, process))
                trigger = True
                break
                
        # 한 번 실행한 프로세스는 큐에 넣지 않고 그대로 종료
        if not trigger:
            answer += 1
            
            if target:
                return answer

 

- 실제 코드

def solution(priorities, location):
    queue = [(i == location, p) for i, p in enumerate(priorities)]
    answer = 0
    
    while queue:
        target, process = queue.pop(0)
        
        if any(process < p[1] for p in queue):
            queue.append((target, process))
        else:
            answer += 1
            if target:
                return answer