알고리즘 풀이: [프로그래머스] 프린터

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

코딩테스트 연습 - 프린터

 

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

 

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

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

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

 

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

 

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

 

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

 

제한 사항

현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.

 

인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.

 

location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

 

입출력 예

priorities	location	return
[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 순으로 인쇄합니다.

---

문제 풀이

프린터는 큐에 대응합니다. 따라서 문서의 중요도는 큐에 원소로서 들어갑니다. 문서 출력은 큐의 헤드(가장 앞자리)에서만 이루어지고, 조건에 따라서 큐 연산(push, pop)을 수행합니다. 그에 따라 요청 문서의 인덱스인 location의 위치 조정이 필요합니다.

 

 

큐 연산의 조건을 살펴봅시다.

준비 단계: 변수 설정 및 큐 연산 조건 설정

문서의 중요도는 큐(프린터)의 원소로 들어갑니다. 그리고 큐의 헤드(HEAD, 가장 앞자리)에 있는 문서의 중요도가 최댓값이라면, 해당 문서는 출력됩니다(pop 연산). 출력과 함께 출력 횟수 역시 증가합니다. 반면에 큐의 헤드에 있는 문서의 중요도가 최댓값이 아니라면, 최대 중요도를 가진 문서가 먼저 출력되어야 하므로, 헤드에 있는 문서는 큐의 테일(가장 뒷자리)로 이동하여 대기합니다(pop 연산 이후 push 연산).

 

이 과정에서 요청한 문서를 가리키는 location의 변화를 주목해야 합니다. 큐에 pop 연산이 수행되면 원소는 도식상으로 모두 한 칸씩 당겨집니다. 따라서 요청한 문서를 가리키는 location 역시 1 만큼 감소해야 합니다. 

 

요청한 문서를 가리키는 location 값이 0이 되면 어떻게 될까요? location 값이 0 인 경우 현재 요청한 문서가 큐의 헤드에 위치합니다. 따라서 요청한 문서가 출력될지 혹은 큐의 가장 뒷자리로 이동할지를 판별해야 합니다. 만약 큐의 헤드에 있는 문서의 중요도가 최대 중요도인 경우 요청한 문서는 출력됩니다. 요청한 문서가 출력되었으므로 더 이상의 반복을 종료하고 지금까지의 출력 횟수를 반환하면 문제를 해결할 수 있습니다. 만약 문서의 중요도가 최대 중요가 아닌 경우 요청한 문서는 큐의 가장 뒷 가지로 이동하고 location 값도 큐의 마지막 인덱스가 됩니다.

 

 

1단계: 0번째 문서

 

1 - 1 단계(왼쪽): 문서 출력 여부 판정 && 1 - 2 단계(오른쪽): 문서 출력 대기

 

 

0번째 문서의 중요도는 1이므로 현재 프린터(큐)에 있는 최대 중요도 9보다 작습니다. 따라서 0번째 문서는 출력되지 않고 대기해야 합니다. 이러한 과정은 큐 연산 pop과 push를 통해 이루어집니다.

 

1 - 3 단계: location 값 조정

location 값을 조정해야 합니다. pop 연산이 수행되었기 때문에 큐에 있는 문서는 모두 한 칸씩 앞으로 당겨졌습니다. 원래 location 값이 0이었기 때문에 큐의 가장 마지막으로 이동합니다.

 

 

2단계: 1번째 문서

2 단계: 문서 출력 여부 판정 → 문서 출력 대기 → location 값 조정 (왼쪽에서 오른쪽으로)

1번째 문서 역시도 중요도에 있어서 최댓값이 아닙니다. 따라서 큐의 가장 뒤에서 대기를 해야 합니다(pop + push). pop 연산을 수행하였기 때문에 location 은 한 칸 앞으로 당겨집니다.

 

 

3단계: 2번째 문서

3 단계: 문서 출력 여부 판정 → 문서 출력 + 횟수 증가 → location 값 조정 (왼쪽에서 오른쪽으로)

2번째 문서의 중요도는 프린터에 있어서 최대 중요도인 9입니다. 따라서 2번째 문서는 출력될 수 있습니다(pop). 출력과 함께 출력 횟수를 1 증가시킵니다. pop 연산을 수행하였기 때문에 location은 한 칸 앞으로 당겨집니다.

 

 

4단계, 5단계: 3번째 문서, 4번째 문서

 

4 단계: 문서 출력 여부 판정 → 문서 출력 + 횟수 증가 → location 값 조정 (왼쪽에서 오른쪽으로)

5 단계: 문서 출력 여부 판정 → 문서 출력 + 횟수 증가 → location 값 조정 (왼쪽에서 오른쪽으로)

 

3번째 문서와 4번째 문서는 각각 해당 문서를 출력하는 시점에서 최대 중요도를 가지고 있습니다. 따라서 3단계에서처럼 출력되고 그에 따라서 location 값이 조정됩니다.

 

 

6단계: 0번째 문서

6 단계: 문서 출력 여부 판정 → 문서 출력 + 횟수 증가 → 반복 종료 (왼쪽에서 오른쪽으로)

다시 돌아온 0번째 문서의 출력 판정 기회입니다. 이번에는 location 값이 0이기 때문에 요청한 문서에 대해서 출력 여부를 판정합니다. 요청한 문서의 중요도는 1로 프린터(큐)에 있는 중요도의 최댓값입니다. 따라서 요청한 문서는 출력되고 그에 따라 횟수도 증가합니다(pop). 요청한 문서가 출력되었기 때문에 더 이상의 반복은 없습니다.

 

 

최종적으로 요청한 문서는 5번째로 출력됩니다.

최종 단계

 

소스 코드

메인 솔루션 함수

from collections import deque


def solution(priorities, location):
    queue = deque(priorities)
    counter = 0

    while queue:
        max_priority = max(queue)
        priority = queue.popleft()

        if priority == max_priority:
            counter += 1
            if location == 0:
                break
            else:
                location -= 1
        else:
            queue.append(priority)
            if location == 0:
                location = len(queue) - 1
            else:
                location -= 1

    return counter


if __name__ == '__main__':
    assert solution([2, 1, 3, 2], 2) == 1

 

프로그래머스 문제 해결

 

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%ED%94%84%EB%A6%B0%ED%84%B0.py

dhsong95/-PRACTICE-Programmers-Algorithm