[백준/JAVA] 1966번: 프린터 큐

🔺 문제

1966번: 프린터 큐

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        while(T --> 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
           
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            LinkedList<int[]> queue = new LinkedList<>();    // Queue로 활용할 연결 리스트
            
            st = new StringTokenizer(br.readLine());
            for(int i = 0 ; i < N ; i++) {
                queue.add(new int[] {i, Integer.parseInt(st.nextToken())}); // 들어온 순서대로 중요도 측정
            } 
            
            int cnt = 0;    // 출력 횟수
            
            while(!queue.isEmpty()) {    // 한 케이스에 대한 반복문
                boolean isMax = true;       // front 원소가 가장 큰 원소인지를 판단
                int now[] = queue.remove(); // 큐 맨 앞 값
                
                // 🔔 탐색 🔔 큐에 남아있는 원소들과 중요도 비교 (자기보다 큰 값이 있으면 뒤로 넘기기)
                for(int i = 0 ; i < queue.size() ; i++) {
                    
                    // 처음 뽑은 원소보다 큐에 있는 i번째 원소가 중요도가 클 경우
                    if(now[1] < queue.get(i)[1]) {
 
                        // 뽑은 원소 및 i 이전의 원소들을 뒤로 보냄
                        queue.offer(now);
                        for(int j = 0 ; j < i ; j++) {
                            queue.offer(queue.poll());
                        }
                        
                        isMax = false;
                        break;
                    }
                }
                 
                // front 원소가 가장 큰 원소라면 해당 원소 출력
                if(isMax) {
                    cnt++;
                    if(now[0] == M) break;
                }
            }
            sb.append(cnt).append("\n");
        }
        
        System.out.print(sb);
    }
}

✅ 해결 아이디어
✔ 큐
- 현재 큐의 가장 앞에 있는 문서의 '중요도' 확인
- 나머지 문서들 中 현재 문서보다 중요도가 높은 문서가 하나라도 있으면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치. / 그렇지 않다면 바로 인쇄

 

💥 유의사항

•  Queue 인터페이스로 받을 수 X. ⇨ get 메소드가 없기 때문.

 

 

---

🔺 다른 풀이들

- Queue(인덱스와 중요도 저장)랑 PriorityQueue(중요도 높은 순 정렬)를 만들어 푸심

백준 1966번 프린터 큐 [JAVA]

 

 

 

- 코드가 제일 짧음

[JAVA] 백준 1966번 - 프린터 큐

 

 

- 설명 짱.. (복습용)

[백준알고리즘-JAVA]1966번 풀이(프린터 큐) - 초보도 이해하는 풀이

---

💬 느낀 점

으앙 만만하지 않구나...

 

 

1회독	2회독	3회독	4회독	5회독
6.20	12.6	12.24	240223

 

 

(+ 2회독 12.6)

get 메소드를 사용하고자 큐를 LinkedList로 선언했다.

LinkedList에 (위치, 중요도)를 저장하는 객체를 변수로 받았다.

 

놓친 부분

뒤쪽에 더 큰 중요도를 가진 원소가 있다면, 뽑은 원소와 그 인덱스 이전까지의 원소들을 모두 뒤로 보내는 과정 (구현)

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        
        while(T --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            
            LinkedList<Node> q = new LinkedList<>();    // 🔔 큐를 LinkedList로 선언해 get 메소드 사용
            
            st = new StringTokenizer(br.readLine(), " ");
            for(int i = 0 ; i < N ; i++) {
                q.add(new Node(i, Integer.parseInt(st.nextToken())));   // 위치와 중요도 입력받기
            }
            
            int cnt = 0;
            
            while(!q.isEmpty()) {
                boolean isMax = true;   // 맨 앞 원소의 중요도가 가장 큰지 확인용 변수
                Node first = q.poll();  // 맨 앞 원소
                
                // 🔔 큐에 남은 원소들과 중요도 비교
                for(int i = 0 ; i < q.size() ; i++) {
                    // 뒤쪽에 더 큰 중요도를 가진 원소가 있다면
                    if(first.val < q.get(i).val) {
                        
                        // 💥 뽑은 원소와, i번째 이전까지의 원소들을 모두 뒤로 보냄
                        q.add(first);
                        for(int j = 0 ; j < i ; j++) {
                            q.add(q.poll());
                        }
                        
                        isMax = false;
                        break;
                    }
                }
                
                // 맨 앞 원소의 중요도가 가장 큰 경우
                if(isMax) {
                    cnt++;
                    if(first.idx == M) break;
                }
            }
            sb.append(cnt).append("\n");
        }
        
        System.out.println(sb);
    }
}
 
class Node  {
    int idx, val;   // 위치와 중요도 저장
    
    public Node(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }
}
 

 

---

(참고)

✔ 풀이 참고

[백준] 1966번 : 프린터 큐 - JAVA [자바]