[BOJ 길라잡이/Java] 11일차 #1966 프린터 큐

알고리즘 분류

- 구현

- 자료 구조

- 시뮬레이션

- 큐

https://www.acmicpc.net/problem/1966

 

내가 찾고자 하는 문서가 몇 번째로 인쇄되는지 출력하는 문제다.

프린터기는 다음과 같이 동작한다.

1. 현재 Queue의 가장 앞에 있는 문서의 '중요도'를 확인한다.

2. 나머지 문서들을 돌며 현재 문서보다 중요도가 높으면, 현재 문서를 Queue의 가장 뒤로 이동시킨다.

3. 현재 문서가 가장 중요도가 높은 문서라면 인쇄한다.

4. 인쇄하는 문서가 내가 찾고자 하는 문서라면 중단하고 몇 번째 인쇄인지 출력한다.

 

처음에 생각한 방법은

내림차순 정렬을 해서 찾는 거였는데, Queue의 특성을 사용하기도 어렵고,

예외사항이 너무 많아서 생각하다가 중단했다..

 

찾아보니 Queue를 LinkedList로 구현해서 최초 순서와 중요도를 저장하는 방법이 있었다.

- 문서마다 [index, priority] 형식으로 큐에 저장한다.

- 가장 앞에 있는 문서를 꺼낸다.

- 꺼낸 문서보다 더 높은 중요도를 가진 문서가 큐 안에 있다면 꺼낸 문서를 큐의 맨 뒤로

- 아니라면 그 문서를 출력하면서 count++ 한다.

- 내가 찾고자 하는 문서라면 몇 번째 출력인지 count를 출력한다.

 

import java.io.*;
import java.util.*;
 
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());

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            LinkedList<int[]> q = new LinkedList<>();
            
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                // {초기 위치, 중요도}
                q.add(new int[] {j, Integer.parseInt(st2.nextToken())});
            }

            int count = 0;

            while (!q.isEmpty()) {
                int[] front = q.poll(); // 가장 앞에 있는 원소
                boolean isMax = true; // front 원소가 가장 큰 원소인지 판단

                for (int j = 0; j < q.size(); j++) {
                    if (front[1] < q.get(j)[1]) { // 중요도 비교
                        q.add(front); // 뽑은 원소를 뒤로 보낸다

                        for (int k = 0; k < j; k++) {
                            q.add(q.poll()); // j이전의 원소들도 뒤로 보낸다
                        }

                        // front가 가장 큰 원소가 아니었음 -> false
                        isMax = false;
                        break;
                    }
                }
                // front가 가장 큰 원소가 아니므로 다음 반복문으로 넘어감
                if (check == false) continue;

                // front가 가장 큰 원소이므로 출력
                count++;
                if (temp[0] == M) break; // 찾고자 하는 문서라면 테스트케이스 종료
            }

            sb.append(count).append("\n");

        }

        System.out.println(sb);
    }
}

 

Queue<Integer> 와 LinkedList<int[]> 사용 차이

내가 여태까지 사용해봤던 방식은

Queue<Integer> q = new LinkedList<>();

이렇게 선언하는 방식이었다.

이때 Queue는 인터페이스, LinkedList는 여러 구현 클래스 중 하나다.

이렇게 쓰면 큐처럼만 사용할 수 있다.

 

add() / offer() : 뒤에 추가

poll() : 앞에서 제거

peek() : 앞에서 보기

그런데 get(index) 같은 메서드는 사용할 수 없다. index를 따로 저장해둘 수 없기 때문이다.

 

오늘처럼

LinkedList<int[]> q = new LinkedList<>();

이렇게 사용하면 큐처럼도, 리스트처럼도 쓸 수 있다.

 

get(index) - 인덱스로 접근

add(index, value) - 중간에 삽입

remove(index) - 특정 위치 제거

이런 메서드들을 추가로 사용할 수 있다.