BOJ_1966_프린터큐_JAVA
문제 : 프린터 큐
링크 : BOJ_1966_프린터 큐
접근 방식
문제 설명을 보자마자 나는 자바의 우선순위 큐 라이브러리를 사용하면 되겠다 라고 생각했다. 하지만 해당 라이브러리를 사용하면서 기존 큐에 들어있던 원래 순번을 확인할 방법을 찾지 못했고, 중복값일 경우 몇 번쨰로 인쇄되는지 찾는데 실패했다. (우선순위 큐에는 제네릭으로 배열을 넣을 수 없었다.)
따라서, 일반 큐를 생성하여 제네릭으로 int[]를 설정, 배열의 첫 번째 인덱스에 초기 위치를, 두 번째 위치에 밸류를 넣어 처리하도록 했다. 일반적인 큐에서는 우선순위로 구별할 수 없기 때문에, 큐를 단방향 순환시키면서 밸류 값이 가장 클 경우 poll시켜주도록 했다. 순차적으로 Poll 시키면서 카운트를 증가시키고, 큐의 초기위치와 주어진 M값을 비교하여 두 값이 같을 경우가 M번째 값이 빠져나오는 순간이다. 그 순간의 카운트 값을 출력하면 된다.
풀이 방법
-
Queue를 선언하여 LinkedList 객체를 생성한다.
-
i=0부터 N만큼 반복, 주어진 입력값을 읽어들여 int 배열으로 Queue에 offer시킨다. 인덱스값인 i는 초기 위치로써 큐에 같이 offer시킨다.
-
위 반복문에서, 우선순위의 값을 정할 int 배열 arr을 만들어 값을 추가로 저장해준다.
-
값이 저장된 배열을 내림차순 정렬하여 높은 값이 가장 앞에 오도록 한다.
-
cnt를 선언하고, while문을 통해 무한반복 시킨다.
-
현재 큐의 front 밸류 값이 원래 값의 최댓값, arr[cnt]보다 작다면 큐를 단방향 순환 시킨다.
-
만약 front 밸류 값이 arr[cnt]보다 크거나 같다면 해당하는 값을 poll해주고, cnt를 1 증가시킨다.
-
7번의 작업이 이루어지기 전에, 큐의 front의 초기 위치를 체크한다. front 값의 초기 위치가 만약 M과 같다면 cnt를 1 증가시키고 출력한 뒤 반복문을 종료한다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
public class BOJ_1966_프린터큐 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
for (int tc = 1; tc <= T; tc++) {
String[] str = in.readLine().split(" ");
Queue<int[]> queue = new LinkedList<>();
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
Integer[] arr = new Integer[N];
String[] str2 = in.readLine().split(" ");
for (int i = 0; i < N; i++) {
// i는 처음위치, 뒤에는 넣은 값이 들어간다.
queue.offer(new int[] { i, Integer.parseInt(str2[i]) });
// 배열의 내림차순 정렬을 통해 우선순위를 체크한다.
arr[i] = Integer.parseInt(str2[i]);
}
Arrays.sort(arr, Collections.reverseOrder());
// System.out.println(Arrays.toString(arr));
int cnt = 0;
while (true) {
// 현재 큐의 가장 앞의 값이 원래 값의 최댓값보다 작으면 큐를 돌린다.
if (queue.peek()[1] < arr[cnt]) {
int[] num = queue.poll();
queue.offer(num);
} else {
if (queue.peek()[0] == M) {
System.out.println(++cnt);
break;
}
queue.poll();
cnt++;
}
}
}
}