BOJ - 1966 - 프린터 큐
문제
문제 개념
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
input
- 4 2
- 1 2 [3] 4
work flow
- 1 2 [3] 4
- 2 [3] 4 1
- [3] 4 1 2
- 4 1 2 [3]
- 4 2 [3] 1
- 4 [3] 2 1
output
- 2
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
using namespace std;
/*
N
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)
M
몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다.
output
궁금 문서의 입쇄 번수
input
3
1 0 - N = 1, M = 0
5 output = 1
4 2 - N = 4, M = 2
1 2 [3] 4 output = 2
4 [3] 2 1
6 0 - N = 6, M = 0
1 1 9 1 1 1 output = 5
workflow
[A] B C D E F
C D E F [A] B
1 2 3 4 [5] 6
output
1 2 5
*/
int a = 0;
int main()
{
int num; // test case
int N; // list size
int M; // 확인할 요소의 index 값
cin >> num;
vector<int> answer;
for(int i=0; i < num; i++)
{
cin >> N >> M;
vector<pair<int, int>> q;
for(int j=0; j < N; j++)
{
int temp;
cin >> temp;
// 우선순위, 초기 순서
q.push_back(pair<int, int>(temp, j));
}
/*
work flow
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
4 2 3 1
4 3 2 1
*/
for(int j=0; j < q.size(); j++)
{
for(int k=j; k < q.size(); k++)
{ // 보다 큰 수를 찾으면
if(q[j].first < q[k].first)
{ // j번째 값보다 큰수가 나올때 까지 pop후 맨 뒤 요소에 push
for(int l=0; l < abs(k - j); l++)
{ // 확인을 하지 않은 앞 요소 저장
int fir = q[j].first;
int sec = q[j].second;
// 큐 pop
q.erase(q.begin()+j);
q.push_back(pair<int, int>(fir, sec));
// work flow 출력
// for(auto el : q)
// cout << el.first << " ";
// cout << "," << k-j << endl;
}
// j번 째 값보다 큰 수가 뒤에도 있을 경우를 대비하여 k값 초기화..
k = j;
}
}
}
// 문서의 출력순서
int count=0;
for(int j=0; j < q.size(); j++)
{
if(q[j].second == M)
{
count++;
answer.push_back(count);
}
else
count++;
}
}
//answer
for(auto &el : answer)
cout << el << '\n';
return 0;
}
SOL
- 맨 앞 요소부터 오름차순으로 정렬하되 큐의 개념을 이용한다.
- work flow
- 1 2 [3] 4
- 2 [3] 4 1
- [3] 4 1 2
- 4 1 2 [3]
- 0번째 index값을 리스트의 가장 큰 요소로 만들면 - 즉 오름차순이 된다면
- 다음 요소로 넘어감..
- 0번째 index값을 리스트의 가장 큰 요소로 만들면 - 즉 오름차순이 된다면
- 4 2 [3] 1
- 4 [3] 2 1