[스택/큐] Level 2 프린터

문제 설명

• 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다.
• 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다.
• 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다.
• 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

• 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.
• 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
• 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예시 및 설명

---

음 이건 "기능개발" 문제보다 어려운 문제였다,,

한 3시간은 넘게 고민한 것 같다,,

deque에 (우선순위, 인덱스)를 리스트로 넣는 것 까지는 생각했는데 자료형이나 조건이 어색해서 결국 다른 사람의 코드를 찾아봤다ㅠㅠ 이건 진짜 내가 풀고 싶었는데,,

하지만 이것또한 성장의 과정이겠찌!!

암튼 알고리즘 설명을 해보자!

 

파이썬 코드)

from collections import deque

def solution(priorities, location):
    answer = 0
    d = deque([(v,i) for i,v in enumerate(priorities)]) #(우선순위, 인덱스)
    
    while d:
        item = d.popleft()
        if d and max(d)[0] > item[0]: #중요도가 가장 높지 않은 문서
            d.append(item)
        else:
            answer += 1 #현재 문서 인쇄(인쇄순서)
            if item[1] == location:
                break
    
    return answer

우선 deque에 (우선순위, 인덱스)를 한 쌍으로 넣는다

그리고 큐가 빌 때까지 반복한다

우선 맨 먼저 들어간 원소를 꺼내준다

그리고 만약에 남은 큐의 최댓값보다 현재 꺼낸 원소가 더 크면 인쇄해도 되고, 아니면 다시 그 아이템을 큐에 넣어야된다

그리고 만약에 인쇄해도 되는 경우에 answer가 인쇄의 순서니까 이를 하나 증가시킨다 -> 인쇄했다는 뜻!

이 때 원하는 위치와 인덱스가 같으면 답이니까 반복문을 중단한다!

여기서 중요한건 if문에서 큐에 다른 원소가 있는지 확인해야 한다!

이거 안해서 테스트케이스에서 에러났다ㅠ

암튼 이렇게 하면 된다

이렇게 보면 또 안어려운것 같은데 생각이 쉽게 나지 않았다

앞으로 더 열심히 해야지!

그럼 안녕~

 

---

야미가 c++ 코드를 들고 돌아왔다~!~!

이 문제를 풀기 위해 c++ STL의 우선순위 큐를 공부하고 왔지ㅎㅎ

자세한건 내 블로그 참고하고 아래는 c++ 코드임

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int count = 0;
    queue<pair<int,int>> q;
    priority_queue<int> pp;
    for(int i=0;i<priorities.size();i++)
    {
        q.push(make_pair(priorities[i],i));
        pp.push(priorities[i]);
    }
    
    while(!q.empty())
    {
        int value = q.front().first;
        int index = q.front().second;
        
        q.pop();
        
        if(pp.top() == value)
        {
            pp.pop();
            count++;
            if(index == location)
            {
                answer=count;
                break;
            }
        }
        else
        {
            q.push(make_pair(value, index));
        }
    }
    
    return answer;
}

알고리즘은 파이썬이랑 동일하고, 달라진건 priority_queue를 사용한거?

간단하게 말하면 우선순위 큐는 데이터를 넣으면 자동으로 큰 값부터 정렬해주는 느낌임

그래서 이 코드에서는 넣고  top()을 호출하면 가장 큰 원소가 출력되기 떄문에 이걸로 문서들의 우선순위를 파악할 수 이쒀

그래서 큐에서 아이템 꺼내서 비교해보고, 우선순위 높은거면 출력하고 count++, 거기다가 location이라 인덱스가 같으면 answer=count로 반환!

만약에 우선순위가 높은게 아니면 걍 make_pair로 만든 쌍을 다시 큐에 넣어주면 됨!

간단한데 priority_queue를 몰라서 오래걸렸따,,

이제 다른 문제 풀러 갈게 빠잉!