[프로그래머스] 프린터 - Stack/Queue

프로그래머스 - 프린터

문제 요약

1. 일반적인 프린터와 다르게 인쇄 대기물에 우선순위를 부여하여 우선순위대로 인쇄물을 출력한다. 즉, 우선 순위에 맞는 순서가 있다.
2. 우선순위 리스트의 첫번째 요소의 값보다 큰 값을 가진 요소가 있다면 첫 번째 요소를 리스트의 가장 뒤로 옮긴다.
3. 이 때 입력으로 주어지는 location 값에 해당하는 문서가 몇 번째로 인쇄되는지 구하여라.

생각

1. 순서가 있기 때문에 가장 우선적으로 Stack과 Queue 자료구조를 떠올렸다.
2. 우선 순위가 뒤로 밀릴 때, 리스트의 가장 뒤로 밀리기 때문에 deque.rotate()를 사용하면 리스트의 pop(), append() 연산에 비해 성능을 챙길 수 있겠고 생각했다.
3. 우선 순위에 따른 문서가 몇 번째인지 알고 있어야 하기 때문에 enumerate()를 사용하여 인덱스 번호를 기억하면 사용이 가능 할 수 있겠다고 생각했다.

코드

from collections import deque


def solution(priorities, location):
    dq = deque([(i, v) for i, v in enumerate(priorities)])
    cnt = 0

    while True:
        if any(dq[0][1] < q[1] for q in dq):
            dq.rotate(-1)
        else:
            tmp = dq.popleft()
            cnt += 1

            if tmp[0] == location:
                return cnt

풀이

예시) priorities = [2, 1, 3, 2], location = 2

1. deque를 사용하기 위해 먼저 import를 해준다.
2. 우선 순위의 인덱스와 우선 순위 값을 함께 tuple로 묶어서 기억한다. 이 예시의 경우 dq = deque([(0, 2), (1, 1), (2, 3), (3, 2)])와 같이 저장된다. 튜플의 첫번째 요소는 인덱스 값이며, 두번째 요소가 실제 우선순위 값이 된다.
3. any() 연산을 사용하여 첫번째 요소의 우선순위 값과 나머지 요소의 우선 순위 값을 비교하여 더 큰 우선 순위 값이 있다면 rotate()를 왼쪽으로 한칸 이동시킨다. 예시의 경우 첫 번째로 2 < 2 를 만족하지 못하여 다음으로 넘어간다. 두 번째로 1 < 2도 만족하지 못하기에 다음으로 넘어간다. 세 번째는 2 < 3 조건을 만족하기 때문에 첫 번째 if절을 수행한다. (any는 any절에 포함된 조건을 하나라도 해당한다면 True를 반환한다.)
4. 조건을 만족했기 때문에 (0, 2) 값은 왼쪽으로 한칸 rotate되어 deque의 가장 마지막으로 이동한다. 즉, deque([(1, 1), (2, 3), (3, 2), (0, 2)])가 된다.
5. any 조건을 만족하지 못한 경우 else 절로 넘어와서 deque의 첫번째 요소 값을 pop 시켜준다. 이는 가장 우선 순위가 높은 인쇄물을 출력했다는 의미이기 때문에 cnt 값을 증가시켜 준다.
6. 마지막으로 5번에서 pop()한 값의 index 값이 입력으로 주어진 location 값과 일치하면다면 그 때, cnt 값을 return 해준다.