[Java] baekjoon_1966 : 프린터 큐

구현, 자료 구조, 시뮬레이션, 큐

프린터 큐 : Silver3

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

1966번: 프린터 큐

 

 

 

풀이

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());
      int M = Integer.parseInt(st.nextToken());

      LinkedList<int[]> q = new LinkedList<>();	// Queue로 활용 할 연결리스트

      st = new StringTokenizer(br.readLine());

      for (int j = 0; j < N; j++) {
        q.offer(new int[]{ j, Integer.parseInt(st.nextToken()) });
      }

      int order = 0; // 몇 번째로 인쇄되는지

      while (!q.isEmpty()) {
        int[] current = q.poll();
        boolean isMax = true; // current 원소가 가장 큰 원소인지를 판단하는 변수

        for(int j = 0; j < q.size(); j++) {

          // 처음 뽑은 원소보다 큐에 있는 j번째 원소가 중요도가 클 경우 
          if(current[1] < q.get(j)[1]) {

            // 뽑은 원소 및 j 이전의 원소들을 뒤로 보낸다.
            q.offer(current);
            for(int k = 0; k < j; k++) {
              q.offer(q.poll());
            }
            
            // current원소가 가장 큰 원소가 아니였으므로 false를 하고 탐색을 마침
            isMax = false;
            break;
          }
        }

        // current 원소가 가장 큰 원소가 아니였으므로 다음 반복문으로 넘어감
        if(isMax == false) {
          continue;
        }

        // current 원소가 가장 큰 원소였으므로 해당 원소는 출력해야하는 문서다.
        order++;
        if(current[0] == M) {	// 찾고자 하는 문서라면 해당 테스트케이스 종료
          break;
        }
      }
      bw.write(String.valueOf(order));
      bw.newLine();
    }
    bw.flush();
    bw.close();
  }
}

 

ㄴ 주어진 중요도를 가지고 문서들을 큐에 넣는다. 각 문서는 [인덱스, 중요도]로 표현된다.
ㄴ 큐에서 하나씩 문서를 꺼내면서, 현재 문서의 중요도가 나머지 문서 중 최대인지 확인한다.
ㄴ 만약 현재 문서의 중요도가 최대라면, 출력 순서 order를 증가시킨다.
ㄴ 현재 문서의 인덱스가 M과 같다면, 반복을 종료하고 최종적으로 얼마나 걸렸는지 출력한다.

 

코드에서 LinkedList를 큐로 사용하여 문서들을 처리하고, 현재 문서의 중요도가 최대인지를 확인하기 위해 반복문을 사용했다.

특히 isMax 변수를 통해 현재 문서가 최대 중요도를 가진 문서인지 여부를 체크하고, 최대 중요도라면 출력 순서를 증가시키고 M과 일치하는지를 확인하여 프로그램을 종료한다.

 

LinkedList

LinkedList는 연결 리스트(linked list)를 구현한 자료구조이다. 

연결 리스트는 노드(node)로 구성된 선형 자료구조로, 각 노드는 이전 노드와 다음 노드의 포인터를 가지고 있다.
LinkedList는 배열과 함께 가장 많이 사용되는 리스트 자료구조이다. 배열과는 달리, LinkedList는 크기가 고정되지 않고 필요에 따라 크기를 조절할 수 있다. 또한, 배열의 경우 맨 앞이나 맨 뒤에 요소를 추가하거나 제거하는 것이 느린 반면, LinkedList는 어디에나 요소를 추가하거나 제거할 수 있다.

LinkedList는 Queue를 구현하는 데 사용될 수 있다. LinkedList의 add() 메서드를 사용하여 요소를 큐의 맨 뒤에 추가하고, poll() 메서드를 사용하여 요소를 큐의 맨 앞에서 제거할 수 있다.

 

add()

값을 리스트의 끝에 추가합니다.

 

offer()

값을 리스트의 끝에 추가하려고 시도한다. 리스트가 가득 차 있으면 false를 반환한다.

 

remove()

리스트의 첫 번째 요소를 제거한다.

 

poll()
리스트의 첫 번째 요소를 제거하고 반환한다. 리스트가 비어 있으면 null을 반환한다.

 

 

참고 블로그

https://st-lab.tistory.com/201

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

 

 

---

 

 

문제점 : 일단 문제 이해를 빠르게 하지 못했고, 큐에 익숙하지 않아 개인적으로는 어려운 문제였다.

해결 방법 : 블로그를 참고하여 문제를 풀었다. 참고한 블로그의 필자는,,, 쉬웠다고,,,, ㅠㅠ 

깨달은 바 : 다양한 알고리즘에 대해 많이 공부를 해야겠다는 생각이 들었다.