[1966] 프린터 큐
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 2 초 | 128 MB | 87682 | 50986 | 40124 | 58.876% |
문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.
출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.
문제풀이
이 문제는 N개의 문서가 규칙에 따라 인쇄될 때 M번째로 입력된 문서의 출력 순서를 구하는 문제이다.
큐의 가장 앞에 있는 문서의 중요도가 남은 문서 중 가장 높다면 출력하고 중요도가 더 높은 문서가 남아있다면 문서를 큐의 가장 뒤로 보낸다.
아래 이미지를 보면 이해가 더욱 쉽다.
숫자와 중요도를 저장하는 클래스 생성
// 숫자와 중요도를 저장하는 클래스 생성
class Document {
int index;
int priority;
Document (int index, int priority) {
this.index = index;
this.priority = priority;
}
}
Document 객체를 저장하고 처리할 수 있는 큐
// Document 객체를 저장하고 처리할 수 있는 큐
Queue<Document> q = new LinkedList<>();
중요도를 저장할 배열 생성
// 중요도를 저장할 배열 생성
Integer[] prioritySequence = new Integer[N];
for (int i = 0; i < N; i++) {
prioritySequence[i] = sc.nextInt();
q.offer(new Job(i, prioritySequence[i]));
}
// 모든 문서의 중요도를 내림차순으로 정렬
Arrays.sort(prioritySequence, Collections.reverseOrder());
반복하며 M번째로 입력된 문서를 출력하기
만약 q의 헤드에 있는 중요도와 현재 중요도순이 다르면 문서를 헤드에서 제거해주고 뒤로 이동해야함.
중요도 순도 맞고 일치한다면 출력을 해줘야하는 것.
for (int i = 0; i < N; i++) {
while (q.peek().priority != prioritySequence[i])
q.offer(q.poll());
if (q.peek().index == M) {
System.out.println(i + 1);
break;
}
q.poll();
}
전체코드
import java.util.*;
class Main {
public static class Document {
int index;
int priority;
Document (int index, int priority) {
this.index = index;
this.priority = priority;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int N = sc.nextInt();
int M = sc.nextInt();
LinkedList<Document> q = new LinkedList<>();
Integer[] proritySequence = new Integer[N];
for (int i = 0; i < N; i++) {
proritySequence[i] = sc.nextInt();
q.offer(new Document(i, proritySequence[i]));
}
Arrays.sort(proritySequence, Collections.reverseOrder());
for (int i = 0; i < N; i++) {
while (q.peek().priority != proritySequence[i])
q.offer(q.poll());
if (q.peek().index == M) {
System.out.println(i + 1);
break;
}
q.poll();
}
}
}
}
시간복잡도
반복문안에 while문을 사용하여 현재 q의 우선순위와 내림차순으로 정렬된 우선순위를 비교한다.
이 때 O(N^2)이 발생한다.
덱
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 0.5 초 (추가 시간 없음) | 256 MB | 93362 | 51965 | 43628 | 56.223% |
문제
정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
- push_front X: 정수 X를 덱의 앞에 넣는다.
- push_back X: 정수 X를 덱의 뒤에 넣는다.
- pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 덱에 들어있는 정수의 개수를 출력한다.
- empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
- front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
문제풀이
이 문제는 양쪽 끝에 원소를 삽입/제거할 수 있는 양방향 Queue - push/pop을 각각 addLast/removeFirst로만 이용하면 FIFO - Queue는 단방향 List만으로 구현할 수 있지만 Deque는 prev/next를 모두 관리하는 양방향 List가 필요하다.
아래 이미지를 보면 이해하기 쉽다.
Deque 분석하기
Deque는 양끝의 삽입/삭제를 제공하는 Collection Queue의 확장 인터페이스 Stack을 대체하여 사용 인덱스 기반 접근을 제공하지 않고 있다.
Deque의 메서드들은 아래와 같이 사용할 수 있다.
Linked List 기반의 Deque 구현
- addFirst/Last: 리스트의 가장 앞/뒤에 새 노드를 연결하여 추가한다.
- removeFirst/Last: 리스트의 가장 앞/뒤 노드에 대한 연결을 끊어 삭제한다.
Array 기반의 Deque 구현
- addFirst/Last: first/lastIndex에 원소를 추가하고 인덱스를 이동한다.
- removeFirst/Last: first/lastIndex의 원소를 삭제하고 인덱스를 이동한다.
import java.io.*;
import java.util.*;
class Main
{
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Deque<Integer> q = new LinkedList<>();
while (N-- > 0) {
String[] cmd = br.readLine().split(" ");
if (cmd[0].equals("push_front")) {
q.offerFirst(Integer.parseInt(cmd[1]));
}
else if (cmd[0].equals("push_back")) {
q.offerLast(Integer.parseInt(cmd[1]));
}
else if (cmd[0].equals("pop_front")) {
bw.write(q.isEmpty() ? "-1\\n" : q.pollFirst() + "\\n");
}
else if (cmd[0].equals("pop_back")) {
bw.write(q.isEmpty() ? "-1\\n" : q.pollLast() + "\\n");
}
else if (cmd[0].equals("size")) {
bw.write(q.size() + "\\n");
}
else if (cmd[0].equals("empty")) {
bw.write(q.isEmpty() ? "1\\n" : "0\\n");
}
else if (cmd[0].equals("front")) {
bw.write(q.isEmpty() ? "-1\\n" : q.peekFirst() + "\\n");
}
else if (cmd[0].equals("back")) {
bw.write(q.isEmpty() ? "-1\\n" : q.peekLast() + "\\n");
}
}
bw.flush();
}
}
'알고리즘 > Queue' 카테고리의 다른 글
| [코딩테스트] [Queue] [10845] 큐 & [15828] Router (1) | 2025.01.21 |
|---|