[프로그래머스] 프린터

문제 보기

이 문제는 스택/큐 문제이다.

문제를 읽다보면 처음에 중요도가 더 높은 문서를 인쇄해야한다고 해서, 우선순위 큐를 생각했었지만, 입력값의 범위가 100보다 작다고 명시되어 있어서 그냥 n^2의 복잡도로 문제를 풀었다.

문제를 푼 로직은 다음과 같다.

 

1. 빠른 삽입과 제거를 위해 주어진 대기목록의 list형 변수를 deque로 변환한다. (7~10번째 줄)
2. 대기 목록의 가장 앞에 있는 문서를 꺼내고, 대기 목록 중에 우선순위가 더 높은 문서가 있는지 확인한다. (13~21번째 줄)
3. 만약 대기 목록 중, 우선순위가 더 높은 문서가 있다면 대기 목록의 맨 뒤에 현재 문서를 추가한다. (17~21번째 줄)
4. 만약 문서가 추가되었다면, 1번으로 되돌아간다. (23~25번째 줄)
5. 만약 문서가 출력되었다면, 횟수를 센다. (26~27번째 줄)
6. 5번에서 출력한 문서가 찾고자 하던 문서라면 종료한다. (29~31번째 줄)

 

여담으로, 7~10번째 줄을 다음과 같이 줄일 수 있다는 것을 다른 사람의 코드를 보고 깨달았다.

# make deque
q = deque([(idx, priority) for idx, priority in enumerate(priorities)])

 

from collections import deque
 
 
def solution(priorities, location):
    answer = 0
 
    # make deque
    q = deque()
    for idx, priority in enumerate(priorities):
        q.append((idx, priority))
 
    while q:
        job_idx, job_priority = q.popleft()
 
        delayed = False
        for idx, priority in q:
            # if current job is delayed
            if job_priority < priority:
                q.append((job_idx, job_priority))
                delayed = True
                break
 
        # don't count if the job is delayed
        if delayed:
            continue
        # add count printed
        answer += 1
 
        # if found the job
        if job_idx == location:
            break
 
    return answer