[백준] 1966번 : 프린터 큐

문제

 

---

풀이

 

대충 상상을 해보자

지금 프린터를 하려는 문서 하나를 띄워놓고 있고(front) 프린트 버튼만 누르면 되는데 이 문서보다 우선 순위가 높은 문서가 있다면 그걸 먼저 출력해야 한다. 그래서 뒤에 대기 중인 문서를 하나하나 살펴보며 우선순위를 확인하는데, 만약 이 문서보다 더 높은 순위의 문서가 있다면 다시 대기줄의 맨 뒤로 보낸다.(pop->push) 이걸 반복하면 된다. 우리가 목표로 하는 문서가 출력될 때까지.

---

소스코드

 

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

struct paper { //우선순위와 체크여부 저장
    int pri;
    bool checked;
};

bool endLoop(queue <paper> q) { //타겟 데이터가 빠지면 루프 종료
    queue <paper> tmp = q;

    while (!tmp.empty()) {
        if (!tmp.front().checked)
            return false;
        tmp.pop();
    }
    return true;
}

bool canPrint(queue <paper> q) { //우선순위 비교하며 프린트 가능여부 확인
    queue <paper> tmp = q;
    int key = tmp.front().pri;

    tmp.pop();
    while (!tmp.empty()) {
        if (key < tmp.front().pri)
            return false;
        tmp.pop();
    }
    return true;
}

int main() {
    int T, N, M;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        queue <paper> q;
        for (int j = 0; j < N; j++) {
            int num;
            cin >> num;
            if (j == M) //타겟 데이터의 checked를 false로 설정
                q.push({ num, false });
            else
                q.push({ num, true });
        }
        int cnt = 0;
        while (!endLoop(q)) {
            while (!canPrint(q)) { //우선순위가 밀린다면 뒤로 옮겨줌
                paper temp = q.front();
                q.pop();
                q.push(temp);
            }
            q.pop(); //프린트
            cnt++;
        }
        cout << cnt << '\n';
    }
}

전체 소스코드다.

 

struct paper { //우선순위와 체크여부 저장
    int pri;
    bool checked;
};

문서의 정보를 구조체에 저장한다. pri는 문서의 우선 순위를 저장하고, checked는 우리가 타겟으로 하는 문서를 표시한다.

 

bool endLoop(queue <paper> q) { //타겟 데이터가 빠지면 루프 종료
    queue <paper> tmp = q;

    while (!tmp.empty()) {
        if (!tmp.front().checked)
            return false;
        tmp.pop();
    }
    return true;
}

반복문의 종료조건이다.

목표로 하는 문서를 제외한 모든 문서는 checked=true이다. 목표 문서가 출력됐을 시 해당 문서의 checked를 false에서 true로 수정할 것이다. 그러니까 큐의 모든 데이터의 checked 값이 true라면 반복문을 종료할 수 있는 것이다.

 

bool canPrint(queue <paper> q) { //우선순위 비교하며 프린트 가능여부 확인
    queue <paper> tmp = q;
    int key = tmp.front().pri;

    tmp.pop();
    while (!tmp.empty()) {
        if (key < tmp.front().pri)
            return false;
        tmp.pop();
    }
    return true;
}

front, 그니까 맨 앞에 있는 문서에 대해 이 문서를 출력할 수 있는지 확인한다.

해당 문서의 pri값을 key로 저장한 뒤 나머지 문서의 pri와 비교하면 된다.

 

        int cnt = 0;
        while (!endLoop(q)) {
            while (!canPrint(q)) { //우선순위가 밀린다면 뒤로 옮겨줌
                paper temp = q.front();
                q.pop();
                q.push(temp);
            }
            q.pop(); //프린트
            cnt++;
        }

main 부분이다. endLoop와 canPrint 함수를 이용해 출력 가능 여부와 반복문 종료 가능 여부를 확인한다.

우선 순위가 밀린 문서는 맨 뒤로 옮겨주고 프린트 할 때마다 그 횟수를 센다.