# priorities = [2, 1, 3, 2], location = 2 -> 1
# 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2일 때
# 인쇄되는 순서: C D A B
# -> 나머지 대기목록에서 중요도가 같은 문서가 있을 때도 J를 가장 마지막으로 보냄
## 의사코드 ##
# 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냄 -> 선입선출 (큐)
# 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에, 그렇지 않으면 J를 인쇄
# => deque(양방향 큐)
# deque 생성
# 1) 맨 첫 번째 원소(j)를 꺼냄
# 2) if 나머지 원소들 중에 중요도가 더 높은 문서가 있으면 -> max() >= j
# 꺼냈던 원소를 deque의 가장 마지막에 추가
# else: 인쇄
# 위의 과정 계속 반복
deque
큐의 앞, 뒤에서 삽입과 삭제가 가능한 큐(=> 양방향 큐)
파이썬의 list와 비슷함
list 대신 deque를 사용하는 이유
시간복잡도 때문
list의 삭제 연산: O(n)
deque의 삭제 연산: O(1)
from collections import deque
첫 번째 시도
from collections import deque
def solution(priorities, location):
answer = 0
deq = deque([(i, v) for i, v in enumerate(priorities)]) # (대기목록 순서, 중요도)
while len(deq):
j = deq.popleft() # 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냄
if max(deq)[1] >= j[1]: # 나머지 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면
deq.append(j) # J를 대기목록의 가장 마지막에 삽입
else: # J보다 중요도가 높은 문서가 존재하지 않으면
answer += 1
if j[0] == location: # j의 원래 대기목록 순서가 location이면
break
return answer
-> 실행 시간 초과로 실패
if max(deq)[1] >= j[1]부분 때문에 실행 시간 초과됨
통과한 코드
from collections import deque
def solution(priorities, location):
answer = 0
deq = deque([(i, v) for i, v in enumerate(priorities)]) # (대기목록 순서, 중요도)
while len(deq):
j = deq.popleft() # 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냄
if any(j[1] < d[1] for d in deq): # 나머지 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면
deq.append(j) # J를 대기목록의 가장 마지막에 삽입
else: # J보다 중요도가 높은 문서가 존재하지 않으면
answer += 1
if j[0] == location: # j의 원래 대기목록 순서가 location이면
break
return answer
-> any()로 해결
any()
인자로 받은 요소 중 하나라도 참(True)이 있으면 True, 모든 요소가 거짓(False)일 경우에만False
iterable 자료형을 인자로 받음
인자로 받은 요소가 비어있는 경우 -> False
all()
인자로 받은 모든 요소가 참(True)이면 True, 하나라도 거짓(False)이면 False
