[프로그래머스]프린터

문제 설명

queue인데 다음과 같은 우선순위를 고려하는 큐이다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

priorities = [2, 1, 3, 2]

문서의 우선순위가 위와 같이 주어졌을 때, 특정 위치(location)에 있는 문서가 몇 번째에 출력될 것인가?

제한사항(조건)

1<=priorities.length<=100 (priorities의 길이)

1<= priorities[i] <= 9 (i는 [0,priorities.length]사이 임의의 수)

0 <= location <= priorities.length-1

접근

주어진 절차에서 2. 를 제외하면 일반 큐와 동일하다. 즉, 2.를 어떻게 처리하느냐가 핵심이다.

나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한개라도 존재하지 않으면 출력한다.

p = 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한개라도 존재한다

=> 나머지 인쇄 대기목록에서 어떤 문서는 J보다 중요도가 높다.

~p => 나머지 인쇄대기목록에서 모든 문서는 J보다 중요도가 높지 않다.

​ => 모든 i에 대하여, x_i <= J (x_i는 인쇄대기목록에 존재하는 문서)

​ => J>=x_i

q = 출력한다

즉," J가 모든 문서에 대해서 우선순위가 높거나 같다면 출력한다." 가 된다.

따라서 나머지 모든 문서를 고려하는 과정이 핵심이 되며, 이는 두가지로 접근할 수 있다.

1.완전탐색

priorites의 길이를 보면 최대 100이다.

매 인쇄물마다 priorities를 모두 찾아봐야 한다. (n번 탐색)

그런데 최악의 경우 마지막에 가서야 pop할 수 있는 것을 찾는다면 n번 반복해야한다 (n번)

이때 인쇄물 1개만 빠지는 것이므로 n개 모두 빠지게 한다면

결국 O(n^3)의 시간 복잡도가 된다.

최대 백만번 연산이므로 충분히 1초 이내에 풀이가 가능하다.

2.우선순위 큐

priorities자체를 우선순위 큐에 집어넣고 이를 pop하며 확인한다면, 동일한 우선순위를 가지는 문서의 순서가 뒤바뀔 수 있다. 뒤바뀐다면 틀리므로 이는 잘못된 방법. (예제 2를 보면 확인할 수 있다.)

따라서 우선순위큐에 priorites를 넣은 뒤, 이는 2. 를 고려하는 용도로 사용한다.

1. priorities를 pop()
2. MaxHeap에서 pop한 수가 문서 내 가장 우선순위가 높은 수이므로 priorites에서 pop한 수가 MaxHeap에서 나온 수보다 크거나 같다면 문서출력가능
3. 작다면 다시 priorities에 넣는다. 이떄 MaxHeap에도 pop한 수를 다시 넣어야 한다.

이렇게 한다면 우선순위를 고려할 때 모든 수를 확인하지 않아도 되므로 시간복잡도는 O(n) -> O(logN)이 된다.(MaxHeap 삽입 시간복잡도)

(한편으로, 다른 사람 풀이를 참고했을 때 MaxHeap보다는 priorities를 sort한 list를 만든 다음에 에 맨 끝(가장 큰 값)만 넣고 뻬면 된다. -> 삽입도 시간복잡도 1이 되서 더 빠름.)

구현

from queue import PriorityQueue
from collections import deque

class MaxPQ:
    def __init__(self):
        self.pq = PriorityQueue()

    def put(self,num):
        self.pq.put(-num)

    def get(self):
        return -self.pq.get()

    def isEmpty(self):
        return self.pq.empty()

def solution(priorities, location):
    #1. priorities 우선순위 큐에 담기
    pq = MaxPQ()
    for p in priorities:
        pq.put(p)

    #2. priorities를 index과 결부
    n = len(priorities)
    waitingDocs = deque(zip(priorities,range(n))) #우선순위, index

    #3. priorities의 앞 값이 우선순위 큐의 값과 동일하다면 pop
    turn = 0
    while True:
        #일단 해당 경우 빼봐
        priority, index = waitingDocs.popleft()
        curMaxPriority = pq.get()

        #뺏을 때 우선순위가 가장 높지 않으면 다시 집어넣어
        if priority != curMaxPriority:
            waitingDocs.append((priority,index))
            pq.put(curMaxPriority)

        #그게 아니면 그대로 빼.
        else:
            turn += 1
            #그런데 찾으려는 인덱스도 동일해? 그럼 굳.
            if index == location:
                break

    answer = turn
    return answer

요즘은 어떻게 해야 깔끔하게 논리를 작성할 수 있는지에 대해 고민하고 있다.

1. 코딩테스트같은 경우 MaxHeap같은 걸 굳이 직접 구현할 필요없이 라이브러리를 이용할 수 있고,
2. 기본적인 DFS,BFS,DP등은 곧바로 구현할 수 있기 때문.

그런 취지에서 이문제를 처음 접근했을 때 논리를 수정하였다.
처음 접근은 다음과 같다.

1. 문서를 pop()

2. 우선순위가 같다면

   turn += 1

   1) index가 찾으려는 location이라면,

   2)아니라면 pass

3. 우선순위가 같지 않다면

   다시 집어넣기

이렇게 구성했는데 if else 문이 2개나 있어서 복잡해졌다.

그래서 정말 문제에서 주어진 문장 그대로 구현하니 코드가 좀 더 깔끔해졌다.

흐음... 그래서 요즘은 논리 연산 에 대해 관심을 가지고 있다.

if문과 같은 분기점에 대해서 적용할 수 있을 것 같은 느낌이 든다.