코딩테스트/Baekjoon
[백준] 1066번: 프린터 큐/ Java 11
soooy0
2025. 6. 12. 18:07
- 실패, 정답보고 이해하고 풀이
https://www.acmicpc.net/problem/1966
프린터 큐
한국어
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 2 초 | 128 MB | 92560 | 54117 | 42638 | 59.152% |
문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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
* - 테스트 케이스의 두번째 줄: N개 문서의 중요도(1 ~ 9 이하의 정수, 중요도가 같은 문서가 여러 개 존재 가능)
*
* ::::: 구현 :::::
* - 테스트 케이스 개수 입력 받고 for 문으로 반복
* - StringTokenizer 로 공백 기준으로 나누어, 문서의 개수와 큐의 몇번째의 놓인 문서를 찾아야 하는지 저장
* - 그 다음 br.readLine()으로 중요도 입력받아서, 큐에 add
* */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.StringTokenizer;
public 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 i = 0; i < T; i++){
// queue 생성
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
ArrayDeque<Integer> arrayDeque02 = new ArrayDeque<>();
// 문서의 개수, 큐의 몇번 째에 놓여진 수 인지 저장
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int doc = Integer.parseInt(st.nextToken()); // 4
int queue_num = Integer.parseInt(st.nextToken()); // 2
// 중요도 저장
StringTokenizer st02 = new StringTokenizer(br.readLine(), " ");
// HashMap 생성
HashMap<Integer, Integer> map = new HashMap<>();
for(int j = 0; j < doc; j++){
int num = Integer.parseInt(st02.nextToken());
arrayDeque.add(num);
map.put(j, num);
}
// arrayDeque 👉 [1, 2, 3, 4]
// map 👉 {0=1, 1=2, 2=3, 3=4}
// 여기서 key = 2 (queue_num)인 값을 찾아야 함
// 출력 순서 구해보기
while(!arrayDeque.isEmpty()){
int first = arrayDeque.poll();
int next = arrayDeque.peek();
if(first < next){
arrayDeque.add(first);
} else {
arrayDeque02.add(first);
arrayDeque.poll();
}
}
System.out.println(arrayDeque02);
}
}
public static void solve(){
}
}- 완벽하게 완성된 코드는 아니었으나.. 아무튼 이렇게 HashMap을 사용해서 문서의 순번과 중요도를 연결해서 저장해려고 시도했으나.. 잘 해결이 되지 않았다.
- 다른 정답코드들을 보니 LinkedList를 사용해서 풀이한 것들이 대부분이었는데.. 나는 무슨 오기가 생겼는 지 ArrayDeque를 사용하고 싶었다.
결론적으로 해결한 풀이
/*
* ::::: 문제 :::::
* - 프린터 기기는 명령을 받은 순서대로, 먼저 요청된 것을 먼저 인쇄한다.
* - 여러개의 문제가 쌓인다면 큐 자료구조처럼 인쇄가 되는 것.
* - 하지만 상근이는 새로운 내부 소프트웨어를 개발함. 이 프린터기는 다음과 같은 조건으로 인쇄됨
*
* - 현재 큐에 가장 앞에 있는 문서의 "중요도" 확인
* - 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 큐의 가장 뒤에 재배치
* 그렇지 않다면 바로 안쇄
*
* - 현재 큐에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내야 함
*
* ::::: 입력 :::::
* - 테스트 케이스는 두 줄씩 이루어짐
* - 가장 첫 줄: 테스트 케이스의 수
* - 테스트 케이스의 첫번째 줄: 문서의 개수 N개, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 몇번째에 놓여 있는 지 나타내는 정수 M
* - 테스트 케이스의 두번째 줄: N개 문서의 중요도(1 ~ 9 이하의 정수, 중요도가 같은 문서가 여러 개 존재 가능)
*
* ::::: 구현 :::::
* - 테스트 케이스 개수 입력 받고 for 문으로 반복
* - StringTokenizer 로 공백 기준으로 나누어, 문서의 개수와 큐의 몇번째의 놓인 문서를 찾아야 하는지 저장
* - 그 다음 br.readLine()으로 중요도 입력받아서, 큐에 add
* */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main{
static class Document{
// 문서의 순서, 원래 위치
int index;
// 위 index 순서별 중요도
int priority;
Document(int index, int priority){
this.index = index;
this.priority = priority;
}
}
public static void main(String[] args) throws IOException {
// 입력받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 테스트 케이스 개수
int T = Integer.parseInt(br.readLine());
// 테스크 케이스 수 만큼 반복
for(int i = 0; i < T; i++){
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// 문서의 개수
int N = Integer.parseInt(st.nextToken()); // 4
// 궁금한 위치
int M = Integer.parseInt(st.nextToken()); // 2
// 중요도 읽기
st = new StringTokenizer(br.readLine(), " ");
// queue 생성
ArrayDeque<Document> arrayDeque = new ArrayDeque<>();
// 큐에 문서위치, 중요도 저장
for(int j = 0; j < N; j++){
arrayDeque.add(new Document(j, Integer.parseInt(st.nextToken())));
}
// 출력되는 순서, 몇번째로 출력되는지 구해야함
int printOrder = 0;
while(!arrayDeque.isEmpty()){
// 현재 비교 중인 문서 저장, 맨 앞에 있는 문서 꺼냄
Document current = arrayDeque.poll();
// 현재 문서보다 더 높은 우선순위가 있는지 나머지 큐에서 확인
boolean hasHigherPriority = false;
for(Document doc : arrayDeque){
// 현재 문서보다 더 큰 우선순위가 뒤에 존재한다면
if(current.priority < doc.priority){
// 더 큰 우선 순위가 있으므로 true 변경
hasHigherPriority = true;
// 맨 앞에 있던 문서를 뒤로 다시 add
arrayDeque.add(current);
break;
}
}
// 큐 전체를 다 비교한 이후에도 여전히 hasHigherPriority 가 false 로 유지되고 있다면,
// 현재 우선순위보다 더 큰 우선순위는 없다는 의미이므로 출력 해주어야 함.
if(!hasHigherPriority){
// 더 큰 우선 순위가 없다면 프린트 진행
printOrder++;
// 만약, 현재 출력되는 문서의 index 가 M과 동일하다면, printOrder 출력순서 출력 후 종료
if(current.index == M){
System.out.println(printOrder);
break;
}
}
}
}
}
}
- 어떤 분의 정답코드를 보고 이렇게 클래스를 활용해서 구현할 수도 있구나 싶어서 해봤다!
- 약간 조금 색다른 흐름이라 코드 하나하나 주석을 달면서 공부하고 다시 코드를 혼자서 작성해보면서 했다.