1966번: 프린터 큐
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에
www.acmicpc.net
큐에 저장되어있는 중요도가 높은 순서대로 pop을 해야합니다.
저는 인덱스와 중요도 관리를 해주기 위해 큐에 배열(중요도, 인덱스)을 넣었습니다.
그리고 중요도가 입력되면 현재 최댓값을 저장하기 위해 몇번 나왔는지(num[])와 최댓값 (maxp)를 사용하였습니다.
그리고 다음과 같은 과정을 수행합니다.
1. 큐에서 원소하나를 pop
2. pop한 원소가 현재 최대 중요도인지 확인 -> 최대 중요도가 아니면 다시 큐에 push합니다.
3. 최대 중요도이면 인덱스가 M과 일치하는지 확인 -> 일치하면 그대로 출력하고 리턴합니다.
4. 인덱스가 맞지 않으면 num[x]을 1 내리고, 만약 num[x]이 0이 되었을 때 다음 최댓값을 꺼내옵니다.
이 과정을 반복하여 M번 인덱스가 몇 번째로 pop되는지 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Queue<int[]> q = new LinkedList<>();
static int num[] = new int[10];
static int N, M, maxp;
static void func() {
while (true) {
int x = q.peek()[0];
int idx = q.peek()[1];
q.remove();
if (x != maxp)
q.add(new int[] { x, idx });
else {
if (idx == M) {
sb.append(N - q.size() + "\n");
return;
}
num[x]--;
if (num[x] == 0) {
for (int i = x; i >= 1; i--) {
if (num[i] > 0) {
maxp = i;
break;
}
}
}
}
}
}
static void input() throws Exception {
int x;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
x = Integer.parseInt(st.nextToken());
q.add(new int[] { x, i });
num[x]++;
maxp = Math.max(maxp, x);
}
}
static void clear() {
maxp = 0;
for (int i = 1; i <= 9; i++)
num[i] = 0;
while (!q.isEmpty())
q.remove();
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
clear();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 10866 덱 (0) | 2021.02.02 |
|---|---|
| boj 11000 강의실 배정 (0) | 2021.02.01 |
| boj 2164 카드2 (0) | 2021.02.01 |
| boj 10845 큐 (0) | 2021.02.01 |
| boj 1655 가운데를 말해요 (0) | 2021.02.01 |