[Python] 프로그래머스 Lv2_프린터

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

프로그래머스

 

• 중요도가 높은 문서를 먼저 인쇄
• 인쇄 작업 수행 절차
  • 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냄
    1. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣음
    1. 그렇지 않으면 J를 인쇄
• priorities: 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열
• location: 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지
• 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 존재
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현

 

"""
입출력 예시)

priorities = [2, 1, 3, 2], location = 2 -> 1
priorities = [1, 1, 9, 1, 1, 1], location = 0 -> 5
"""

 

# 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
  • iterable 자료형을 인자로 받음
  • 인자로 받은 요소가 비어있는 경우 -> True

 

 

cf) 이전에 작성했던 코드

 

https://monzheld.tistory.com/53

[Python] 프로그래머스 Lv2_프린터

 

 

 

참고)

 

https://velog.io/@nayoon-kim/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque

[파이썬] deque

 

https://j-ungry.tistory.com/189

파이썬 collections deque 함수 (덱,데크) 사용법

 

https://velog.io/@kho5420/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-any-%EC%99%80-all-%EC%96%B8%EC%A0%9C-%EC%96%B4%EB%96%BB%EA%B2%8C

[Python] 파이썬 any 와 all 언제 어떻게?