[Programmers] Python 프로그래머스 프린터 Level 2

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

코딩테스트 연습 - 프린터

 

큐를 사용하면 쉽게 풀 수 있는 문제이다.

 

스택과 큐에 대해 익숙하지 않거나 까먹었다면 먼저 이전 포스팅을 참고하여 이해하고 오는 것을 추천한다.

2021.12.04 - [알고리즘/알고리즘 강의] - [알고리즘] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

[알고리즘] 스택(Stack)과 큐(Queue) 데크(Deque)까지 (Python)

 

문제풀이

---

눈여겨봐야 할 점은 3가지다.

 

1. 대기목록에서 꺼낸 문서보다 중요도가 높은 문서가 대기목록에 남아있다면 꺼낸 문서를 다시 대기 목록에 넣는다.
2. 대기 목록에는 최대 100개의 문서가 있다.
3. 중요도는 숫자가 클수록 중요하다.

대기 목록인 priorities의 첫 원소를 차례대로 빼면서 나머지 원소 중 최대 중요도를 비교하여 뺀 문서보다 중요도 높은 문서가 있다면 뒤에 추가하는 형식으로 풀면 될 것이다.

 

이때 최대 100개의 문서밖에 없으므로 O(n)의 시간 복잡도를 가지는 max 함수로 최대 중요도를 비교하면 된다.

 

동시에 location에 해당하는 문서가 몇 번째에 출력되는지 묻는 문제이므로 원소를 pop 할 때마다 location을 감소시키고 음수가 되면 대기 목록의 마지막에 추가되었다고 생각하면 된다.

 

간단한 문제이므로 바로 전체 코드로 넘어가겠다.

 

def solution(priorities, location):
    answer = 0
    while len(priorities)>0:        #대기 목록에 문서가 있는 동안 반복
        temp=priorities.pop(0)      #첫 번째 문서 꺼내기
        if len(priorities)==0:      #껴낸 문서가 마지막 일때 종료
            answer+=1
        else:
            if temp>=max(priorities):   #꺼낸 문서의 중요도가 제일 높을 때
                if location==0:         #찾고자 하는 문서일 때 종료
                    answer+=1
                    break
                else:
                    location-=1
                    answer+=1
                        
            #꺼낸 문서보다 중요도가 높은 문서가 대기 목록에 존재할 때
            else:
                priorities.append(temp)
                location-=1
                if location<0:
                    location=len(priorities)-1
    return answer

 

3번째 줄은 대기 목록에 문서가 있는 동안 반복하기 위해 while문을 선언하였고  4번째 줄은 pop(0)을 통해 0번째 인덱스의 원소를 제거하며 반환한다.

 

또한 5번째 줄은 꺼낸 문서가 마지막 문서일 때 (더 이상 대기 목록에 문서가 없을 때) 고려할 조건이 없으므로 answer을 증가시킨 후 바로 종료한다.

 

8번째 줄의 if문은 max로 대기 목록의 중요도를 비교하여 더 높은 중요도가 없으면 출력하는 문서로 판단하고 location을 감소시킨다.

 

이때 location이 0이라면 꺼낸 문서가 찾는 문서이므로 answer을 증가시킨 뒤 break를 통해 반복문을 빠져나온다.

 

17번째 else는 대기 목록에 더 높은 중요도가 있을 때 뒤에 추가하는 구문으로 만약 location이 음수가 되면 대기 목록의 마지막에 추가했다는 의미이므로 현재 priorities 길이의 -1로 변경하면 된다.

 

결과 화면

 

이 문제는 Input Size가 상당히 작아서 굳이 시간 복잡도를 계산할 필요까진 없었던 것 같다.

 

조건만 잘 확인하고 구현한다면 충분히 쉽게 통과할 수 있을 것이다.

 

이 프린터 문제는 우선순위 큐란 알고리즘이다.

 

다만 우선순위 큐는 힙(Heap)이란 자료 구조를 사용하고 내부 구조에서 최댓값, 최솟값을 갱신하는데 O(logn)의 효율적인 시간 복잡도를 가진다.

 

파이썬은 Heapq란 모듈을 통해 쉽게 우선순위 큐를 구현 가능하며 해당 문제에서는 큐를 연습하기 위해 일부러 Input을 적게 주고 우선순위 큐의 결과를 나타낼 수 있도록 유도한 것 같다.

 

코테에서도 은근히 우선순위 큐를 사용하는 문제가 나오므로 우선순위 큐를 구현하는 힙에 대해서 포스팅하겠다.