1966번 - 프린터 큐
문제 풀이 시간 :
문제 요약
- 여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음
- 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄
- 그렇지 않으면 바로 인쇄
- 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제
문제 풀이
이 문제는 프린터의 동작을 그대로 구현하면 되는 시뮬레이션 문제다.
처음에는 문서의 순서를 관리하는 큐와 현재 가장 높은 중요도를 빠르게 확인하기 위한 우선순위 큐를 함께 사용해서 풀었다.
큐에는 (문서의 원래 위치, 중요도)를 넣고 우선순위 큐에는 중요도만 따로 넣어 현재 가장 높은 중요도를 peek()로 확인하는 방식이다.
즉,
- 맨 앞 문서를 하나 꺼낸다.
- 그 문서의 중요도가 현재 가장 높은 중요도와 다르면 다시 큐 뒤로 보낸다.
- 같으면 인쇄하고, 우선순위 큐에서도 하나 제거한다.
이 방식도 충분히 정답 처리가 가능하고 처음 떠올리기에도 가장 자연스러운 풀이였다.
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
// 현재 가장 높은 중요도를 빠르게 확인하기 위한 우선순위 큐
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
return Integer.compare(o2, o1);
});
// (문서의 원래 위치, 중요도) 저장
Queue<int[]> q = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int priority = st.nextToken().charAt(0) - '0';
pq.add(priority);
q.add(new int[]{i, priority});
}
int cnt = 0;
while (!pq.isEmpty()) {
int[] now = q.poll();
// 현재 최고 중요도가 아니면 뒤로 보냄
if (pq.peek() != now[1]) {
q.add(now);
continue;
} else {
// 최고 중요도 문서라면 인쇄
pq.poll();
cnt++;
}
// 찾고 있는 문서라면 종료
if (now[0] == m) {
break;
}
}
System.out.println(cnt);
}
}
}하지만 다시 보니, 이 문제에서 중요도는 1~9까지만 존재한다.
즉, 굳이 우선순위 큐를 사용할 필요 없이 각 중요도가 몇 개 남아 있는지만 배열로 관리해도 충분했다.
그래서 나는
- 문서의 순서를 관리하는 큐
- 현재 남아 있는 중요도 개수를 저장하는 배열
을 같이 사용하는 방식으로 바꿨다.
배열로 각 중요도의 개수를 세어두고 현재 남아 있는 가장 높은 중요도 max만 따로 관리하면
- 맨 앞 문서의 중요도가
max가 아니면 뒤로 보냄 max와 같으면 바로 인쇄
이렇게 처리할 수 있다.
문서를 하나 인쇄할 때마다 해당 중요도의 개수를 줄이고 현재 최고 중요도가 더 이상 남아 있지 않으면 max를 감소시키며 갱신하면 된다.
우선순위 큐를 쓰는 풀이보다 구조도 단순하고 이 문제의 조건을 더 잘 활용한 방식이라고 생각했다.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] priorities = new int[10];
Queue<int[]> q = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
int max = 0;
// (문서의 원래 위치, 중요도) 형태로 큐에 저장
for (int i = 0; i < n; i++) {
int priority = Integer.parseInt(st.nextToken());
priorities[priority]++;
q.add(new int[]{i, priority});
max = Math.max(max, priority);
}
int cnt = 0;
while (!q.isEmpty()) {
int[] now = q.poll();
// 현재 최고 중요도가 아니면 뒤로 보냄
if (now[1] != max) {
q.add(now);
continue;
}
// 현재 문서 인쇄
cnt++;
priorities[now[1]]--;
// 찾고 있는 문서라면 종료
if (now[0] == m) {
break;
}
// 현재 최고 중요도가 더 이상 없으면 갱신
while (max > 0 && priorities[max] == 0) {
max--;
}
}
System.out.println(cnt);
}
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.
17070번 - 파이프 옮기기 1
크기 N × N 격자에서 파이프를 이동시키는 경우의 수를 구하는 문제 파이프는 항상 2칸을 차지하며, 방향은 총 3가지 시작 상태는 (1,1) ~ (1,2) 가로 방향 파이프의 한쪽 끝이 (N, N) 에 도달하는 모든 경우의 수를 계산 처음 문제를 읽었을 때는 👉 그래프…