[Python] (스택/큐) 프린터

문제 설명

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

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

def solution(priorities, location): 
    i = 0
    answer = location + 1
    if len(priorities) == 0:
        return 0
    while True:
        i += 1
        if priorities[0] < priorities[i]:
            priorities.append(priorities[0])
            priorities.pop(0)
            answer -= 1
            if answer == 0:
                answer = len(priorities)
            i = 0
            continue
        if i == len(priorities) - 1:
            break
    return answer

몇몇 테스트 케이스만 통과했다.

위 코드의 문제점을 알아본 결과, 위 코드는 그냥 가장 큰 숫자가 맨 앞에 존재하면 프로그램이 종료된다.

따라서 후순위 출력물들은 중요도에 관계없이 출력된다는 것이다.

문제 이해를 잘못한 탓에 코드도 일부 케이스만 통과하도록 작성됐다.

 

성공 #1

def solution(priorities, location):
    length = len(priorities)
    priority_min = 0
    while True:
        before = priorities
        before_location = location
        for i in range(1, len(priorities)):
            if priorities[0] < priorities[i]:
                priorities.append(priorities[0])
                priorities.pop(0)
                location -= 1
                if location < priority_min:
                    location = length - 1
                break
        if before == priorities and before_location == location:
            priorities.pop(0)
            if location == priority_min:
                break
            priority_min += 1
        if not priorities:
            break
    return location + 1

• lenght는 for문의 i의 범위를 정하기 위해서, priority_min은 location이 위치할 수 있는 최소 위치를 정하기 위해서 설정한 변수이다.
• before와 before_location은 만약 for문이 실행되지 않아서 맨 앞의 원소를 빼야할 때 조건을 판단하기 위해 둔 변수이다. location까지 둔 이유는 혹시나 for문이 동작해서 원소를 뒤로 보냈는데 똑같은 함수가 있지 않을까 생각해서 두었다.
• for문에서는 만약 1개라도 맨 앞의 원소보다 큰 경우가 있는 경우, 맨 앞의 원소를 맨 뒤로 삽입하고 맨 앞의 원소를 제거, 그 이후 location에 -1을 더하도록 작성했다. 만약 location이 가장 최소로 위치할 수 있는 priority_min보다 작아진다면 가장 후순위가 대입되도록 if문을 추가로 작성했다.
• 아래의 if문은 모양이 1번이라도 바뀌지 않는다면 맨 앞의 원소가 중요도가 제일 높으므로 맨 앞의 원소를 제거하라는 의미로 두었다. 그리고 priority_min에 1을 더한다. 맨 앞의 원소가 제거되면서 인쇄의 순서는 맨 앞으로 위치할 수 없기 때문이다.
• 그리고 마지막 if문에서는 혹시나 중요도가 맨 마지막이어서 끝까지 제거가 될 때까지 남아있는 경우, 모든 원소가 제거되면 break를 실행하도록 작성했다.
• location에 1을 더한 값을 반환하도록 하였다.

 

다른 사람 풀이

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

• enumerate를 이용하여 우선순위에 인덱스를 붙인 튜플을 queue에 넣는다.
• 현재의 값의 변수인 cur에 큐의 첫번째 원소를 대입한다.
• any() 함수: 이게 풀이의 핵심이다. if 조건문에서 단 한번이라도 True가 있다면 True를 반환한다. 즉, 현재의 값보다 큐에 들어 있는 q[1]값이 단 한개라도 크다면 if문이 실행되어 큐의 맨 끝에 현재의 값 cur을 넣는다.
• 그렇지 않다면 answer(인쇄 순서)에 1을 더한다.
• 만약 cur[0]가 location과 같다면 우리가 인쇄하려던 문서가 인쇄되어 pop되었음을 의미하므로 answer를 return한다.

 

끝으로

정말 간편한 함수 any()를 배워가게 되었다.