[Queue/구현] BAEKJOON 1966번 '프린터 큐'문제(c++/python)

문제 : www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

• 문제 해결 아이디어

    1.  문제의 흐름을 따라 코드를 작성한다. (최대 들어오는 data값이 100, 제한시간이 2초이므로 흐름에 따라 작성해도 충분하다.)

 

    2.  현재 큐에서 priority의 최대값과, 큐의 가장 앞문서의 priority값이 같은지 확인한다.

 

    3.  같다면 인쇄한다는 의미로 count를 증가시키고, 인쇄하는문서의 index번호와. 찾으려는 문서의 번호가 같은지 확인한다.

 

          3-1.  같다면 count를 출력한다.

 

          3-2.  다르다면 현재 문서를 pop으로 큐에서 제거하고 다음으로 넘어간다.

 

    4.  다르다면 큐 앞에있는 문서를 빼서 큐의 가장 뒤에 넣는다.

 

 

 

 

• python

test_case = int(input())

for _ in range(test_case):
    n, m = list(map(int, input().split(' ')))
    queue = list(map(int, input().split(' ')))
    queue = [(i, idx) for idx, i in enumerate(queue)]

    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            # queue에 속해있는 요소들 중 가장 큰 priority와,
            # 가장 앞 인자의 priority를 비교한다. (lamda함수 활용)
            
            count += 1
            if queue[0][1] == m:
                print(count)
                break
            else:
                queue.pop(0) # list를 queue처럼 활용하기 위해서 pop(0).
                # 이는 performance측면에서 성능이 떨어진다. 
                # 때문에 collection package의 dequeue를 import해서 사용하는것이 빠르다.
                # (https://jacoblog.tistory.com/2)
        else:
            queue.append(queue.pop(0))

 

 

※ enumerate

 

      리스트의 index값을 표기하기위해 사용한다.
      enumerate 함수 사용시 enumerate 객체를 return한다.

data= enumerate((1,2,3))
print(type(data))       # 출력 : <Class enumerate>

      enumerate 객체는 (index, data) 순서로 저장된다.

 

 

 

 

 

• c++

    index와 priority를 함께 저장하기 위해서 pair를 사용하였다.

    hightest_priority 함수를 만들어, 현재 큐의 최대값을 찾도록 하였다.

 

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

int highest_priority (queue<pair<int,int>> q){
    int size = q.size();
    int max=0;
    pair <int, int> p;
    
    for(int i = 0 ; i< size; i++){
        p = q.front();
        q.pop();
        if(p.second > max)
            max = p.second;
        q.push(p);
    }
    return max;
}


int main(){
    
    int n,m,test_case, max_num, count;
    queue<pair<int,int>> q;
    pair<int,int> tmp;
    
    cin >> test_case;
    
    for(int i=0 ; i< test_case ; i++){
        count = 0;
        cin >> n >> m;
        
        for(int j=0 ; j< n ; j++){
            int tmp;
            cin >> tmp;
            q.push(make_pair(j, tmp));
        }
        
        while(1){
            max_num = highest_priority(q);
            
            if(max_num == q.front().second){
                int num = q.front().first;
                q.pop();
                count++;
                if(num == m){
                    break;
                }
            }
            else{
                tmp = q.front();
                q.pop();
                q.push(tmp);
            }
        }
        
        while(!q.empty())
              q.pop();
        
        cout << count << "\n";
        
    }
    return 0;
}