https://www.acmicpc.net/problem/1966
◆ 문제 풀이
우선순위에 따라 규칙이 있는 큐를 구현하여, 원하는 문서가 언제 pop되는지 출력하는 문제입니다.
기본적으로 큐를 구현하되, 몇 가지를 추가로 고려하여야 합니다.
■ 찾는 문서를 기록할 별도의 배열 혹은 2차원 배열이 필요
입력 1 1 9 1 1 1 예시를 보면 같은 숫자가 배열에 포함되어있으므로, 단순히 [1이 out되는 경우 출력하는것]으로는 문제를 해결할 수 없습니다.
따라서, 원하는 문서를 표시할 별도의 배열이 필요합니다.
■ 기본적인 선형 탐색과 Que 알고리즘
가장 앞의 값과 뒤의 값들을 비교해, 더 큰 수가 있다면 앞의 값을 뒤로 밀어넣은 후, 제거합니다.
이 때, 위에서 언급한 추가 배열도 같은 과정을 진행해야 원하는 수가 out될때, 인식할 수 있습니다.
■ out과 카운트
더이상 뒷 배열에 더 큰 수가 없을 경우, 프린트한것으로 간주하고 앞에서 하나를 지웁니다.
이 때, 카운트를 누적시켜, 몇 번 프린트되었는지 체크하고, 만약 이번에 프린트된 것이 원하는 문서라면, 카운트를 저장합니다.
◆ 코드
#include <iostream>
#include <vector>
using namespace std;
//프린터큐
int main() {int num;
cin >> num;
int *counts = new int[num];for (int k = 0; k < num; k++) {
int size, key, temp;
cin >> size >> key; // 사이즈와 키를 입력받음
vector<int> arr;
vector<int> chk;for (int i = 0; i < size; i++) {
cin >> temp;
arr.push_back(temp);
if (i == key) { // 원하는 숫자일 경우, 1을 넣어 마킹.
chk.push_back(1);
}
else { // 원하는 숫자가 아닌 경우 0으로 초기화.
chk.push_back(0);
}
}
int mark = 0;
int count = 0;
while (mark == 0) {// 원하는 숫자가 출력될때까지 무한 반복한다.// 숫자가 하나일 경우 예외
if (arr.size() == 1) {
count++;
break;
}for (int i = 1; i < arr.size(); i++) { // 반복문이 끝난 후 : 한 번의 회전이 끝난다.
if (arr.front() < arr.at(i)) { // 맨 앞의 값과 i번째 값을 비교, 더 큰 숫자가 있으면
arr.push_back(arr.front());
arr.erase(arr.begin());
chk.push_back(chk.front()); // chk값도 마찬가지로 처리
chk.erase(chk.begin());
break;
// arr[0]의 값을 뒤로 밀어넣는다. 반복문 탈출.
}
if (i == arr.size() - 1) { // 끝까지 와버렸어... 더이상 큰수가 없어...
if (chk.front() == 1) {// 배열을 뺄 때, 해당하는 chk배열에 마킹이 되어있으면, 전체 탈출 후, mark값을 표기해 전체탈출
count++;
mark = 1;
break;
}
else { // 아닐 경우(이번숫자이긴 한데 원하는숫자는 아니면) 숫자 빼고 카운트만 올려줌.
arr.erase(arr.begin());
chk.erase(chk.begin());
count++;
}
}
}
}
counts[k] = count;
}for (int k = 0; k < num; k++) {
cout << counts[k]<<"\n";
}
// arr와 chk 초기화해야함. 아니면 반복문에 넣던가.
return 0;
}
by. 구 본철