[프로그래머스/파이썬] 프린터

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

문제 링크(Programmers Level2)

---

프로그래머스

---

문제 풀이

---

 

처음에는 PriorityQueue 모듈을 이용해서 풀려고 했는데, 원소를 꺼냈을 때 현재 값이랑 비교해서 뒤로 넘길 방법이 떠오르지 않았다.

그래서 그냥 큐를 이용해서 풀었다.

1. 0부터 입력리스트 숫자만큼 차례대로 리스트를 생성해서 큐에 넣어준다.
2. 입력 리스트도 큐에 넣어준다.
3. 큐에 원소가 없을 때 까지 루프 돌면서 먼저 큐에서 가장 큰 값을 m에 넣고, temp에 큐의 첫번째 원소를 넣는다.
4. 만약 m이랑 temp랑 같지 않다면 현재 그 원소가 빠질 차례가 아니라는 뜻이므로, 다시 큐에 temp를 넣어준다. 그러면 가장 뒤로 원소가 옮겨지게 된다. 그리고 문서 이름을 나타내는 n의 원소도 뒤로 넘겨준다.
5. m이랑 temp랑 같다면 현재 그 원소가 빠질 차례인 것이므로, n에서도 원소를 빼내고 카운트를 1 증가시킨다. 이때, n에서 빼낸 원소와 location의 값이 같다면 카운트를 리턴하고 종료한다.

---

코드

---

from collections import deque

def solution(priorities, location):
    num=[i for i in range(len(priorities))]
    
    q=deque()
    n=deque()
    for i in priorities:
        q.append(i)
    for i in num:
        n.append(i)
    
    cnt=0
    while q:
        m=max(q)
        temp=q.popleft()
        if not m==temp:
            q.append(temp)
            t=n.popleft()
            n.append(t)
            
        else:
            t=n.popleft()
            cnt+=1
            if t==location:
                return cnt

다른 사람의 코드

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

any라는 함수가 있더라. 처음 봤다.

그리고 enumerate 이용해서 큐에 우선순위랑 문서이름 동시에 넣는다.

루프 돌면서 큐에서 하나씩 꺼내주고 any를 이용해서 빼낸 원소보다 큐에 우선순위가 더 큰 것이 있다면, 다시 큐에 빼낸 원소를 넣어주고

그게 아니라면 카운트를 1 증가시킨 뒤에, 문서 이름이 내가 찾는 것과 같으면 바로 카운트를 반환시킨다.

로직은 같은데, any 함수를 이용해서 간결하게 표현한 코드라 감명 깊다.

그리고 개인적인 생각으로, pop()을 이용했을 때는 시간복잡도가 N이고, deque를 이용한 popleft()는 시간복잡도가 1이기 때문에, deque를 사용하면 시간복잡도를 줄일 수 있을 것 같다.