[백준] 1966번 : 프린터 큐

문제

 

 

접근 방식

현재 큐에 남아 있는 우선순위 중 가장 큰 값이 등장하기 전까지는

빼서 다시 맨 뒤에 넣어주어야 한다.

 

그렇게 계속 진행하다 현재 값이 가장 큰 값이거나 같다면 빼주고

카운트를 1 증가시켜주면 된다.

 

다만 값을 뺄 때 목표로 하던 값인지를 확인해야 하는데

이를 객체를 하나 생성하여 우선순위와 목표인지 여부를 기록해

큐에 넣고 돌아주면 편리하다.

 

현재 가장 큰 값을 체크하기 위해 우선순위 큐를 사용하였지만

배열에 받아두고 정렬을 하여 값을 꺼낼 때마다

바라보고 있는 인덱스를 1씩 감소시켜도 문제없다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		Queue<Pair> q;
		PriorityQueue<Integer> pq;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());

			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine());

			q = new ArrayDeque<>();
			pq = new PriorityQueue<>((x1, x2) -> x2 - x1);

			for (int i = 0; i < n; i++) {
				int x = Integer.parseInt(st.nextToken());

				q.offer(new Pair(x, i == m));
				pq.offer(x);
			}

			int cnt = 0;

			while(!q.isEmpty()) {
				int max = pq.peek();
				Pair cur = q.poll();

				if (cur.num < max) {
					q.offer(cur);
					continue;
				}

				cnt++;

				if (cur.isTarget) break;
				pq.poll();
			}

			sb.append(cnt).append("\n");
		}

		System.out.println(sb);
	}

	static class Pair {
		int num;
		boolean isTarget;

		public Pair(int num, boolean isTarget) {
			this.num = num;
			this.isTarget = isTarget;
		}
	}
}