[백준 JAVA] 1966 프린터 큐

1966 프린터 큐

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

문제설명

stack을 사용해서 주어진 명령어들(<, >, -, 문자)을 처리하여 최종적으로 입력된 문자열을 반환하는 문제

접근방식

O(n) 선형 시간복잡도

 

각 테스트 케이스마다 문서의 수 N개 만큼 큐 연산을 수행한다.

큐에서 원소 하나를 빼고 모든 원소와 비교하므로 O(N)이 된다.

문제 조건 분석 과정

• 각 테스트 케이스마다 문서의 수 N과 궁금한 문서의 현재 위치 M을 입력받는다.
• 각 문서마다 초기 위치와 중요도를 입력받아 큐에 저장한다.
• 큐에서 문서를 하나씩 꺼내면서 해당 문서보다 중요도가 높은 문서가 있으면 맨 뒤로 보내고,
• 없으면 출력한다.
• 문서가 출력되면 출력된 문서 수를 기록하고 다음 테스트 케이스로 넘어간다.

사용된 자료구조

• LinkedList: 큐로 활용되며, 문서의 초기 위치와 중요도를 저장하고 관리한다.
• int[] 배열: 문서의 초기 위치와 중요도를 각각의 원소로 저장한다.

틀린이유

원소를 큐에서 빼고 삽입하는 과정에 반대로 했기 때문에 틀렸습니다가 떴다.

큐 활용법을 좀 더 공부하자.

올바른 접근 방식 및 해결 방식

• 큐 활용: 문서의 초기 위치와 중요도를 큐에 저장하여 FIFO(선입선출) 구조 활용.
• 비교 및 정렬: 맨 앞에 있는 문서를 꺼내어 나머지 문서들과 비교하여 우선순위에 맞게 정렬.
• 조건 충족: 궁금한 문서가 출력될 때까지 반복하며, 출력된 문서의 수를 카운트하여 결과를 출력.

전체코드

import java.util.*;
import java.io.*;

public class Main_1966프린터큐 {
        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[]> q = new LinkedList<>();	// Queue로 활용 할 연결리스트
                st = new StringTokenizer(br.readLine());

                for (int i = 0; i < N; i++) {
                    // {초기 위치, 중요도}
                    q.offer(new int[] { i, Integer.parseInt(st.nextToken()) });
                }

                int count = 0;	// 출력 횟수

                while (!q.isEmpty()) {	// 한 케이스에 대한 반복문

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

                    // 큐에 남아있는 원소들과 중요도를 비교
                    for(int i = 0; i < q.size(); i++) {

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

                            // 뽑은 원소 및 i 이전의 원소들을 뒤로 보낸다.
                            q.offer(front);
                            for(int j = 0; j < i; j++) {
                                q.offer(q.poll());
                            }

                            // front원소가 가장 큰 원소가 아니였으므로 false를 하고 탐색을 마침
                            isMax = false;
                            break;
                        }
                    }

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

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

                }

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

            }
            System.out.println(sb);
        }

    }