[프로그래머스 42587 파이썬] 프린터 (level 2, 스택/큐)

알고리즘 유형 : 스택/큐
풀이 참고 없이 스스로 풀었나요? : O

https://programmers.co.kr/learn/courses/30/lessons/42587?language=python3

SOLVE 1

직접 푼 풀이(모든 작업을 인쇄하고 각각의 서수를 구한 뒤, 구하고자 하는 순서의 작업의 인쇄 서수를 딕셔너리에서 조회해 출력하는 풀이)

from collections import deque
def solution(priorities, location):
    answer = 0
    order = {} # key: task 순서, value: 인쇄 서수
    task_info = deque(enumerate(priorities)) # 원소는 작업=(순서, 중요도)임.
    
    # priorities를 정렬 후, 높은 중요도 숫자부터 뽑을거임
    # task_info에서 pop한 작업의 중요도가 이 숫자와 같을 때만 작업을 인쇄하도록 할거임
    aim_prio = list(sorted(priorities))
    
    # 작업을 pop하면서, 이 중요도와 비교해서 같으면 인쇄할거임
    cnt_prio = aim_prio.pop()
    
    # 인쇄 서수
    count = 0
    
    # 모든 작업들을 인쇄하고 그때마다 인쇄 서수를 구하여 order에 저장하는 while문
    while task_info:
        order_tmp, prio_tmp = task_info.popleft() # pop한 작업의 info
        if prio_tmp == cnt_prio:
            count += 1
            order[order_tmp] = count
            if aim_prio: # 마지막 작업을 pop하고 난 후 남는 중요도가 없는 상태를 고려한 조건문
                cnt_prio = aim_prio.pop()
        else:
            task_info.append((order_tmp, prio_tmp))
    
    # order에서 서수가 location인 작업의 인쇄 서수를 정답으로 리턴
    answer = order[location]
    return answer

SOLVE 2

pop한 각 작업에 대해 작업 리스트의 모든 작업들과 중요도를 비교하는 풀이

from collections import deque
def solution(priorities, location):
    answer = 0
    
    # (순서, 중요도)를 원소로 갖는 덱
    tasks = deque(enumerate(priorities))
    
    # 모든 작업을 인쇄하거나 인쇄한 작업의 순서가 location과 같을 때까지 반복
    while tasks:
        cnt_order, cnt_prio = tasks.popleft()
        # 남은 모든 작업들 중에 현재 작업 중요도보다 중요도가 높은게 하나라도 있으면
        if any(cnt_prio < task_prio[1] for task_prio in tasks):
            tasks.append((cnt_order, cnt_prio))
        else:
            answer += 1
            if cnt_order == location:
                break
    
    return answer

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

SOLVE 1) 풀이 요약 (모든 작업을 인쇄하고 각각의 서수를 구한 뒤, 구하고자 하는 순서의 작업의 인쇄 서수를 딕셔너리에서 조회해 출력하는 풀이)

1. 순서와 중요도를 튜플로 갖는 덱 task_info

   priorities를 오름차순으로 정렬한 aim_prio

   모든 중요도 경우의 수 중, 가장 큰 중요도부터 차례대로 인쇄하기 위한 비교 변수 cnt_prio

   인쇄 서수 count

2. task_info를 모두 돌면서 모든 작업을 인쇄한다. (while문)

   만약 현재 순회 중인 작업의 중요도가 cnt_prio와 같으면, (남아 있는 작업 중 가장 큰 중요도임) 이 것을 인쇄한다. 즉, count를 1 증가시키고 order에 해당 작업의 순서 키에 인쇄 서수를 저장한다.

   만약 같지 않으면 이 작업을 맨 뒤로 보내기 위해 다시 task_info에 append한다.

3. while 문이 끝나면 order에는 모든 작업들의 인쇄 서수가 담겨있다. 여기서 location을 키값으로 하여 조회하면 그 value가 답이다.

   2번 풀이보다 시간복잡도가 빠르지만, 코드가 길고 복잡하다.

SOLVE 2 풀이 요약 (pop한 각 작업에 대해 작업 리스트의 모든 작업들과 중요도를 비교하는 풀이)

1. (순서, 중요도)를 원소로 갖는 덱 tasks

2. any 함수는 괄호 안의 iterable한 객체의 원소 중에 하나라도 true가 있으면 true, 아니면 false를 반환하는 함수이다.

   만약 현재 남은 작업 중에, 현재 순회 중인 작업의 중요도보다 큰 것이 하나라도 있다면, 현재 작업은 맨 뒤로 보낸다.

   반대의 경우에는, answer에 인쇄 서수를 기록하고(+1), 만약 이 것이 location과 같다면 이 때의 answer이 답이다.

배운 점, 어려웠던 점

• any 함수에 대해 알게 되었다.