스택/큐 프린터_Python_JavaScript

문제 설명

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

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로 표현합니다.

예제 #1

문제에 나온 예와 같습니다.

예제 #2

6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

---

접근 방법

FIFO의 큐를 떠올리는데는 어렵지 않았다. 카테고리에 스택/큐 타이틀이 없었어도 중요도 비교를 위해 큐를 떠올리는것이 어렵지 않았을것 같다!!

location 이라는 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 리턴 값으로 인덱스에 대한 정보가 필요했다.

인덱스에 대한 정보를 어떻게 활용할지 생각하였다.

q = deque(array)

위와 같은 방법으로 배열을 큐로 만들어주는데는 어렵지 않다.

하지만 인덱스 정보를 함께 활용할 수 있는 함수가 있다는 것을 알고있어

enumerate 함수를 찾아 적용할 수 있었다.

v = 중요도
i = 인덱스
q = deque([(v, i) for i, v in enumerate(priorities)])
# deque([(2, 0), (1, 1), (3, 2), (2, 3)])   

리스트 컴프리헨션으로 enumberate 함수를 사용하여 값과 인덱스 모두를 활용한 큐를 만들 수 있었다.

이때 enumerate 함수의 특성으로 i, v 순서가 뒤바뀌지 않도록 주의하자(인덱스 , 값)

이렇게 큐를 만들어주었다면 90% 해결하였다고 할 수 있을 것 같다.

큐의 O(1) popleft()를 이용해 q안에서 처음 추출한 값보다 큰 값이

있으면 맨 뒤에 데이터를 추가하고

없으면 answer += 1 그리고 그때의 frist_data의 인덱스가 location과 같을 경우 반복문을 종료한다.

추출한 값이 가장 큰 경우 또는 추출한 값 보다 큰 값이 없는 경우 q는 계속 삭제되어 결국 비어있게 된다.

---

이때 max 내장 함수를 올바르게 사용해야한다.

(원인을 찾느데 한참 걸렸다.)

q = deque([(v, i) for i, v in enumerate(priorities)])
# deque([(2, 0), (1, 1), (3, 2), (2, 3)])  


1. max(q[0]) => 2   (X)

2. max(q)[0] => 3   (O)

# 반복 가능한 객체는 q[0]가 아니라 q 이다.

max는 반복가능한 객체의 가장 큰 요소를 리턴하는 내장 함수이다.

현재 튜플로 구성되어있는 큐 객체로 q[0]를 반복가능한 객체로 보는 것이아니라, q 자체를 반복가능한 객체로 봐야한다.

문법의 주의가 필요한 부분이다!!

---

from collections import deque

def solution(priorities, location):
    answer = 0
    # v = 중요도, i= 인덱스
    q = deque([(v, i) for i, v in enumerate(priorities)])
    # deque([(2, 0), (1, 1), (3, 2), (2, 3)])     

    while len(q):
        frist_data = q.popleft()
        # deque max 메소드 쓰는법 주의 
        # max(q[0]) => X  // max(q)[0] => O

        if frist_data[0] < max(q)[0]:
            q.append(frist_data)
        else:
            answer += 1
            if frist_data[1] == location:
                break
    
    return answer

---

테스트 케이스 2번, 5번, 18번에서 런타임 에러가 발생한다.

관련 내용을 찾아보니 아래 테스트 케이스와 같이 max함수 사용시 q가 비어버리는 경우가 발생한다.

# [3, 3, 4, 2] location = 3 => 
return = 4

 

따라서 조건문에 q가 비어있을 경우 바로 else로 넘어갈 수 있도록 조건을 추가해줬다.

from collections import deque

def solution(priorities, location):
    answer = 0
    # v = 중요도, i= 인덱스
    # [3, 3, 4, 2] location = 3 => return = 4
    q = deque([(v, i) for i, v in enumerate(priorities)])
    # deque([(2, 0), (1, 1), (3, 2), (2, 3)])     

    while len(q):
        frist_data = q.popleft()
        # deque max 메소드 쓰는법 주의 
        # max(q[0]) => X  // max(q)[0] => O
        # 위 테스트 케이스에서 max 함수가 비는 순간이 발생하므로 q가 존재한다는 조건 추가
        if q and frist_data[0] < max(q)[0]:
            q.append(frist_data)
        else:
            answer += 1
            if frist_data[1] == location:
                break
    
    return answer

---

시간 복잡도

큐를 만드는데 시간 복잡도는 인쇄 대기 목록(priorities) 만큼 반복하므로 => O(N)

while => O(N)

popleft() => O(1)

max 내장함수 => O(N)

append() => O(1)

총 시간 복잡도는 O(N^2)이라고 생각된다.

하지만 제한 사항에서 인쇄 대기 목록은 최대 100개로 제한되어 있어 좋은 효율을 나타내고 있는게 아닐까 한다.

---

JavaScript

최대값이 문제인 코드이다!!

function solution(priorities, location) {
    let count = 0;
    let myList = priorities
    // let maxNumber = Math.max(...myList)
    let myQueue = priorities.map((value, index) =>[value, index])
    //	[ [ 2, 0 ], [ 1, 1 ], [ 3, 2 ], [ 2, 3 ] ]
    // [ [ 1, 0 ], [ 1, 1 ], [ 9, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ] ]
    // [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 0 ], [ 1, 1 ] 1
    while (true){
        let maxNumber = Math.max(...myList)
        const firstValue = myQueue.shift()
        if (firstValue[0] < maxNumber){
            myQueue.push(firstValue)
        } else {
            count += 1
            if (myList.length > 2){
                myList = myList.filter((number) => number !== maxNumber)
            }
            if (firstValue[1] === location){
                break
            }
        }    
    }
    return count
}

---

최대값의 문제가 있어 코드를 변경함!!

파이썬보다 더 빠르게 풀었다!!! 무야호~~

function solution(priorities, location) {
    let count = 0;
    let myQueue = priorities.map((value, index) =>[value, index])
    let myList = priorities.sort((a, b ) => b - a)

    while (true){
        const maxNumber = myList[0]
        const firstValue = myQueue.shift()
        if (firstValue[0] < maxNumber){
            myQueue.push(firstValue)
        } else {
            count += 1
            myList.shift()
            if (firstValue[1] === location){
                break
            }
        }
    }
    
    return count
}