programmers [level2] 프린터 /알고리즘 프로그래머스

문제 주소 : programmers.co.kr/learn/courses/30/lessons/42587

난이도 : Level2

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

 

풀이

- 큐를 구성해놓고 순서가 궁금한 값의 위치를 저장해놓는다
하나씩 빼서 우선순위 맥스 값과 비교하고 최댓값이면 출력 아니면 맨뒤로 추가
이동시킬 때마다 위치 값도 같이 한 칸씩 변환
출력시킬 값의 인덱스가 0번이면 종료

 

답안

def solution(priorities, location):
    nNowPos = location
    answer = 1
    
    while True:
        nTemp = priorities.pop(0)
        if len(priorities) == 0:
            break
            
        if nTemp >= max(priorities):
            if nNowPos == 0:
                break
            else:
                nNowPos -= 1
                if nNowPos < 0:
                    nNowPos = len(priorities)
            answer += 1
        else:
            priorities.append(nTemp)  
            nNowPos -= 1
            if nNowPos < 0:
                nNowPos = len(priorities)-1
    
    return answer

solution([2, 1, 3, 2],2)    


# from collections import deque

# def solution(priorities, location):
#     dpriorities = deque(priorities)
#     nNowPos = location
#     answer = 1
    
#     while True:
#         nTemp = dpriorities.popleft()
#         if len(dpriorities) == 0:
#             break
            
#         if nTemp >= max(dpriorities):
#             if nNowPos == 0:
#                 break
#             else:
#                 nNowPos -= 1
#                 if nNowPos < 0:
#                     nNowPos = len(dpriorities)
#             answer += 1
#         else:
#             dpriorities.append(nTemp)  
#             nNowPos -= 1
#             if nNowPos < 0:
#                 nNowPos = len(dpriorities)-1
    
#     return answer

 

느낀 점

큐로 만든 간단한 문제 파이썬은 리스트를 큐처럼 활용하면 pop 할 때 시간 복잡도가 N이라서 타임아웃이 걱정되었으나 한방에 통과하였다 추후 문제 푼사람들을 보니 deque라는걸 사용하면 pop할 때 시간복잡도가 1이라 해서 비교해보았는데

좌측 list, 우측 deque

100개 이하의 데이터라 그런지 체감이 전혀 안되었다...  오히려 더 느린 부분이 존재하기도 
어쨌건 하나 배워놨으니 나중에 써먹어봐야지
근데 코딩 테스트할 때 라이브러리들을 이렇게 import 해서 사용해도 되는 건가 싶기도 하고..

그리고 분명 level 2에서 너무 어려운 것도 있었는데 지금은 또 너무 쉬워서 3단계로 가야 하나 고민되네 두어 개만 더 풀어보고 정해야겠다