[코딩테스트] 프로그래머스 - 프린터 (Lv.2) in Python

프린터 인쇄 순서

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.

2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.

3. 그렇지 않으면 J를 인쇄합니다.

 

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return.

 

programmers.co.kr/learn/courses/30/lessons/42587

 

풀이

- 배열의 앞에서 원소를 꺼내고, 그 원소가 뒤로 간다는 점이 원형 큐를 떠올리게 했다.

참고 - piaflu.tistory.com/67(따로 정리해봤다!)

[자료구조] 파이썬의 deque - 양방향 큐, 원형 큐 구현

- 배열의 앞에서 원소를 꺼내는 것은 O(n), 원형 큐 / 덱(dequeue)에서 꺼내는 것은 O(1)이기 때문

- 그래서 Python의 deque를 사용하기로 결정! (사실 배열 크기 max.가 크지 않아서 - 최대 100개, 그냥 list를 썼어도 크게 나쁘지는 않았을 것 같다.)

 

 

===========================================

- 매개변수로 주어진 priorities와,

- 순서를 저장하기 위해, index를 저장한 order를 모두 dequeue로 바꿔줌.

 

- priorities에서 맨 앞의 원소를 뽑아냄

     - 나머지 원소들 중 뽑아낸 원소보다 큰 숫자가 있으면

          - 뽑아낸 원소를 도로 맨 끝에 붙임

          - order배열도 마찬가지로 순서를 바꿔줌 - .rotate이용

     - else

          - 뽑아낸 원소를 출력하는 경우

          - order배열의 맨 앞에 있는 숫자도 뽑아서, answer 배열에 넣어준다.

 

- answer배열에서, location에 해당하는 숫자 + 1을 결과로 반환함!

 

파이썬 구현

from collections import deque

def solution(priorities, location):
    priorities = deque(priorities)
    order = deque([i for i,v in enumerate(priorities)])
    answer = []
    
    while priorities:
        fi = priorities.popleft()
        
        if len(priorities)==0 or fi>= max(priorities):
            answer.append(order.popleft())
        else:
            priorities.append(fi)
            order.rotate(-1)
            
    return answer.index(location) + 1

 

다른 분들의 풀이

- any를 이용하고, 인덱스 - 우선순위를 list of tuples로 구성해 깔끔하게 풀어내신 분들의 방법이 인상깊었다. 다음과 같이 복기해본다.

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