우선순위큐 MaxHeap 프린터 힙 알고리즘문제 풀이

 

안녕하세요 민군입니다 ^-^ 오늘은 프로그래머스 2단계 문제 중 하나인 프린터 문제에 대해 살펴보고자 합니다. 프린터 문제에 대해 바로 돌아보겠습니다.

---

 

 

❊우선순위큐 MaxHeap을 사용해서 프린터 알고리즘문제 풀어보기

♣︎ 프린터 알고리즘문제 설명

이 프린터는 우리가 일반적으로 알고있는 프린터의 작동방식이 아닙니다. 프린터할 문서의 우선순위를 판단해 최 우선순위의 문서가 먼저 인쇄되도록 되어있습니다. 

• 1. 대기목록에서 가장 앞에 있는 문서를 꺼내어 가장 중요도가 높은 문서인지 확인합니다. 만약 최우선순위의 문서라면 출력을 바로하지만 그게 아니라면 출력을 보류하고 대기열의 맨 마지막 순서로 높습니다. 
• 2. 이를 반복하다가 최우선순위의 문서가 나오면 이를 출력하는 방식의 최우선순위 우선출력방식의 프린터입니다.

 

 

예를들면 4개의 문서, A,B,C,D가 있고 중요도가 순서대로 2,1,3,2라면 우선순위가 3으로 제일 높은 C가 제일 먼저 출력되야 하기에

A-B-C-D => B-C-D-A => C-D-A-B 순으로 대기열이 바뀌다가 최우선 순위 C문서가 대기열의 맨 앞에 도달하면 이를 출력합니다. 가장 먼저 출력되는 C의 출력순위는 1순위가 됩니다.

 

 

대기목록의 문서는 1~100개, 작업의 중요도는 1~9로 표현되며 숫자가 클 수록 더욱 중요하다는 의미입니다.

location은 0~(대기목록작업수-1)의 크기를 가지며 초기 대기열의 문서 위치를 기준으로 첫번째 위치의 location 값은 0입니다.

 

 

Priorities가 [2,1,3,2]이고 location이 2인 곳의 출력순서를 알아야 한다는 것은 문서대기열의 3의 중요도를 갖는 세번째 문서의 출력순서를 알아야 한다는 것입니다. 대기열 세번째의 3의 중요도를 갖는 문서는 가장 중요한 문서이므로 1번째로 출력되게 됩니다.

이 문제는 어떻게 풀 수 있을까요? 먼저 각 인덱스의 문서초기 인덱스값과 각각의 중요도값을 동시에 저장할 수 있으면 좋겠습니다. 

queue<pair<int,int>> q의 형태로 큐의 페어데이터로 인덱스와 중요도값을 저장하겠습니다.

또한 현재 문서 중 가장 중요한 문서의 우선순위를 쉽게 알기 위해 우리는 우선순위큐(Priority Queue)를 사용 할 수 있습니다.

 

 

♣︎ 프린터 알고리즘문제 풀이

우선순위 큐는 들어가는 순서는 동일하지만 나오는 순서는 가장높은값의 순 혹은 가장낮은값의 순으로 나올 수 있습니다. 

• priority_queue<int, vector<int>, less<int>> pq; 의 경우 max heap으로, 가장 높은 값이 먼저 pop되어 나옵니다.
• priority_queue<int, vector<int>, greater<int>> pq2; 의 경우 min beap으로 가장 낮은 값이 먼저 pop되어 나옵니다.

 

 

answer는 현재 출력되는 순서를 나타낼 것입니다. 본래 문제가 요구하는 정답은 출력순서이기에 자연스럽습니다. 

페어형태의 데이터를 갖는 큐는 프린터의 대기열(인덱스, 우선순위값)을 표현하며 priority_queue는 최우선순위값이 어떤값인지를 확인하기위해 사용합니다.

 

 

먼저 priorities(우선순위값 배열)을 순회하면서 각각의 우선순위값을 같는 문서의 인덱스와 우선순위값을 큐에 넣어주고 우선순위큐에는 우선순위 값만 넣어줍니다.

maxHeap을 설정해놓은 우선순위큐는 우선순위값을 전부 넣으면 가장 높은 우선순위값을 맨 앞에 놓습니다.

 

 

큐가 비어있지 않을때까지(대기열에 출력될 문서가 하나도 없게 될때까지) 그 안에서 대기열을 탐색할 것입니다.

현재 큐(문서대기열)의 맨앞 문서의 인덱스와 우선순위값을 미리 저장해 놓습니다.

 

 

인덱스와 우선순위값을 미리 저장해놓았기 때문에 해당 큐는 빼내어도 문제가 없습니다. 해당 문서가 출력이되던 안되던 결국 pop은 해야하기 때문입니다. *출력이 되면 해당 큐의 값을 그대로 사라지고, 출력이 안되면 해당 큐값은 (대기열 최 후순위)뒤로 다시 들어갑니다.

만약 맨앞 문서의 우선순위가 최우선순위라면 출력을 하는데 이때 출력되는 순서가 문제에서 요구하는 순서라면 이 순서값, answer를 리턴합니다. 그게 아니라면 최우선순위큐를 팝하고 다음 대기열 문서를 바라봅니다.

최우선순위가 아니라면 해당 문서는 대기열의 최 후순위로 다시 들어갑니다.(push()) 이렇게 되면 결과적으로 문제에서 요구하는 특정위치의 문서 출력순위를 알 수 있게 됩니다. 

우선순위큐는 이처럼 최댓값, 최솟값의 정보를 활용해야할 때 매우 유용하게 사용할 수 있습니다.

지금까지 프로그래머스 알고리즘 문제중 하나인 프린터 문제 풀이 포스팅이었습니다. 다음에도 틈나면 포스팅올리겠습니다. ^-^//