[プログラマ]スタック/キュー-プリンタ

プログラマ-プリンタ

問題の説明

キューリストの優先度の高いドキュメントから出力を開始すると、リクエストしたドキュメントの何回目の印刷を返しますか?

せいげんじょうけん

待機ディレクトリに1つ以上のファイルがあります。 印刷作業の重要性は1から9で表され、数字が大きいほど重要です。 locationはキューリストのindexを表します。

問題を解く

リストの一番前のドキュメントよりも後ろのドキュメントが重要であることを確認します。 より重要なドキュメントが後ろにある場合は、一番前のドキュメントを最後に送信します。 より重要なドキュメントがない場合は、一番前のドキュメントを出力します。

コード#コード#

#include <string>
#include <vector>
#include <list>

using namespace std;

list <pair<int, int>> waiting_list;

void Make_list(vector<int> priorities){
    for(int i=0; i<priorities.size(); i++){
        waiting_list.push_back(make_pair(i,priorities[i]));
    }
}

bool Is_first(){
    int front = waiting_list.front().second;
    bool is_first = true;

    list <pair<int, int>>::iterator iter;
    for(iter=waiting_list.begin(); iter!=waiting_list.end(); iter++){
        if(front < iter->second){
            is_first = false;
            break;
        }
    }
    
    return is_first;
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    bool is_first;
    Make_list(priorities);
    
    while(1){
        is_first = Is_first();
        if(!is_first){
            pair<int, int> new_back = waiting_list.front();
            waiting_list.push_back(new_back);
        }
        else{
            answer ++;
            if(waiting_list.front().first == location) break;
        }
        waiting_list.pop_front();
    }
    
    return answer;
}

時間の複雑さ

Worstcase:待機リストがdescending orderの場合、+最後のドキュメントの出力順序はreturnです.
時間の複雑さ:O(N^2)N : 대기목록의 크기

スタック/キューの問題でlistを使用する理由

最初はキューを使用しようとしましたが、文を繰り返してキュー内のすべての要素にアクセスして値を決定する必要があります.
しかしQはindexを使って元素に近づけないので不便です.
要素アクセスが多い場合、listを使用するとスタック/キューよりも自由になり、pop, pushを使用して要素にアクセスすると便利になるため、indexを使用します.

コメントサイト

List of C++