백준 1966번: 프린터 큐

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p1966.java

1. 중요도 입력받기

• 배열 priorities: 중요도만 저장하는 배열 -> 이후 내림차순으로 정렬
• 큐 queue: {문서 번호, 중요도} 리스트를 저장하는 큐 -> 이후 연산에 사용

중요도를 입력받으면서 위의 두 자료구조에 값을 저장한다.

큐에는 데이터 쌍을 저장해야 했는데, 백준 11650번: 좌표 정렬하기처럼 Pair 클래스를 따로 만드는 것은 번거로웠다. 또한 큐에 저장해야 하므로 백준 11651번: 좌표 정렬하기 2처럼 2차원 배열을 사용할 수도 없었다. 그래서 데이터 쌍을 리스트로 만들어서(Arrays.asList() 사용) 큐에 저장하는 방식을 사용하였다.

자바에서 같은 타입의 데이터 쌍을 클래스 안만들고 관리하는 방법은 아래와 같다. (백준에서 record는 못쓰니 제외)

• 데이터 쌍을 배열로 관리: 2차원 배열 만들어서 관리
• 데이터 쌍을 다른 자료구조로 관리: 데이터 쌍을 리스트로 만들고, 리스트를 자료구조에 넣기

inputs = br.readLine().split(" ");
Integer[] priorities = new Integer[N];              // 정렬할 우선순위 배열
Queue<List<Integer>> queue = new LinkedList<>();    // 연산에 사용할 큐 -> {번호, 중요도} 저장

for (int j = 0; j < N; j++) {
	int priority = Integer.parseInt(inputs[j]);

	priorities[j] = priority;
	queue.add(Arrays.asList(j, priority));
}

2. 중요도 내림차순 정렬하기

priorities 배열을 내림차순으로 정렬한다. 그러면 중요도가 높을수록 배열의 앞에 오게 된다.

나중에 큐 연산할 때 priorities 배열을 앞에서부터 차례로 조회할텐데 현재 조회하고 있는 중요도가 가장 높은 중요도이다. 현재 priorities 배열에서 조회하고 있는 중요도를 가진 문서가 프린트되면 그 중요도는 이제 프린트되었으므로 가장 높은 중요도가 아니다. 그러므로 priorities 배열에서 다음 원소를 조회하여 가장 높은 중요도를 갱신한다. 만약 같은 중요도가 여러 개 있으면 priorities 배열에서 다음 원소를 조회하여도 실질적으로 중요도의 최대값은 갱신되지 않겠지만, 그 중요도를 가진 문서 하나가 차감됐다는 의미를 가진다.

Arrays.sort(priorities, Comparator.reverseOrder());

3. 큐 연산하기

사용되는 변수는 다음과 같다.

• head: 큐의 가장 앞에 있는 원소. 리스트이므로 0번은 문서 번호, 1번은 중요도를 저장하고 있다.
• count: 프린트한 횟수. priorities 배열에서 현재 최대 중요도를 조회하는 데에도 쓰인다.

count는 0~N의 범위를 가지는데, 만약 원하는 문서가 가장 나중에 프린트 된다고 했을 때 count가 N이 된다. 이때는 원하는 문서가 프린트 되어서 루프를 탈출하므로 priorities 배열의 인덱스 범위(0~N-1)를 넘어서 조회하는 경우는 없다.

무한 루프를 돌면서 head를 뽑는다.

head의 중요도가 현재 최대 중요도(priorities[count])보다 작으면 프린트 우선순위에서 밀린다는 의미이므로 다시 큐에 넣는다.

head의 중요도가 현재 최대 중요도보다 크거나 같으면 가장 우선순위가 높은 문서이므로 프린트하고, count 값을 1 증가시킨다. count 값이 증가되었으므로 다음 루프 때 현재 최대 중요도를 조회하면 priorities 배열에서 그 다음 원소를 조회하게 된다. 이는 현재 최대 중요도의 문서를 출력하였으므로 다음으로 높은 중요도로 최대 중요도를 갱신하는 역할을 한다. 만약 head의 문서 번호가 몇번째로 인쇄되었는지 궁금한 문서 번호와 같다면 count 값을 출력 버퍼에 넣고 루프를 탈출한다.

while (true) {
	List<Integer> head = queue.remove();

	if (head.get(1) < priorities[count]) {
		queue.add(head);
	}
	else {
		count++;

		if (head.get(0) == M) {
			bw.append(count).append('\n');
			break;
		}
	}
}