[프로그래머스/Level2] 프린터 (C++)

[프로그래머스/Level2] 프린터 (C++)

1.문제

---

2. 접근/체크포인트

1. 우선순위가 같은 문서가 여러 개 있을 수 있기 때문에, 해당 우선순위의 문서 중에서도 내가 찾고자하는 문서의 index(location)과 같은지 확인해야함.
2. 우선순위와 index를 함께 묶어야 확인 가능 -> pair()사용.

---

3. 해결 방법

1. priority_queue(우선순위 큐)를 사용하여 모든 문서를 우선순위 기준 내림차순으로 정렬한다.
   -> 이때, 정렬된 순서가 우선순위 기준(index 신경안쓸 때) 출력 순서.
2. priorities의 index와, 해당 index의 우선순위를 pair()로 묶어 큐에 저장한다.
3. 우선순위 큐가 비거나, 찾고자하는 문서(location)가 나올 때까지 반복하며 출력 과정을 거친다.
4. 우선순위에 맞는 경우(출력 가능한 경우) 큐에서 삭제하고 count(출력 순서 확인용 변수)의 수를 증가시킨다.
5. 우선순위에 안맞는 경우, 다시 큐의 맨 마지막으로 추가된다.

---

4.전체코드

#include <vector>
#include <queue>
#include<utility>  //pair() 사용
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int count = 0;
    
    queue<pair<int,int>> q;  //priorities의 순서(idx)와 우선순위를 쌍으로 저장할 큐
    
    priority_queue<int> pq; //우선순위에 따라 내림차순으로 저장할 우선순위 큐
    
    //pq에 우선순위 저장(내림차순), 큐에 idx와 우선순위 순서쌍 저장
    for(int i=0; i<priorities.size(); i++){
        pq.push(priorities[i]);
        q.push(make_pair(i,priorities[i]));
    }
    
    while(!pq.empty()){  //대기 목록이 없을 때 까지 반복
        
        int idx = q.front().first;
        int val = q.front().second;
    
        //우선순위와 대기 순서가 일치한다면 => 출력
        if(val == pq.top()){
            
            pq.pop();
            q.pop();
            count++;  //출력 순서 count용
            
            if(idx == location){  //해당 문서가 내가 궁금한 인쇄물이라면
                answer = count;  //몇 번째 순서로 출력되는지 확인
                break;
            }
        }else{  //우선순위가 더 높은 문서가 있다면 맨 뒤로 보내기
            q.pop();
            q.push(make_pair(idx,val));
            
        }
        
    }

    
    return answer;
}

---

5. 참고사항

👉 C++의 우선순위 큐 - PriorityQueue

1.queueu 헤더파일 include하기

#include> queue

2. 우선순위 큐 선언

priority_queue<int> pq; 
priority_queue<int, vector<int>, less<int>> pq;

• 두 가지 모두 큰 값부터 정렬되는 내림차순 우선순위 큐(디폴트)

3. 우선순위 큐에 원소 삽입

pq.push(2) 

• 일반 큐에 원소 삽입하는 것과 같은 방법

4. 우선수위 큐의 원소 꺼내기

pq.top() 

• 우선순위 큐의 가장 상위 원소(우선순위가 높은 원소)를 꺼냄

5. 우선순위 큐 오름차순으로 설정하기

priority_queue<int, vector<int>, greater<int>> pq;

• 위 방식으로 선언하면 우선순위 큐가 오름차순으로 설정되어, 가장 작은 값부터 출력.
• 혹은 기본 방식을 사용하고 원소를 push 할 때, 음수로 변경하는 방법도 있음.

---

6.다른 방법으로 풀어보기

추후 추가 예정

---

7. 후기

추후 추가 예정