코딩테스트/코딩테스트

[백준 1966 ] 프린터 큐 JAVA 풀이

90만식 2022. 2. 27. 18:08
728x90
사용언어 : JAVA
문제 URL : https://www.acmicpc.net/problem/1966

1.문제

-문제설명

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

예를 들어 위와 같은 이진 트리가 입력되면,

  • 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
  • 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
  • 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

 

2.입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다

 

3.출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

1.입력
 
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

2.출력
 
1
2
5

 

2.코드구현(JAVA)

 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 키보드로 입력 받기
        Scanner scanner = new Scanner(System.in);
        // 1.테스트케이스 수 입력 받기
        int testcaseCnt = scanner.nextInt();
        //System.out.println(testcaseCnt);

        for(int i=0; i<testcaseCnt; i++){
            // 2.테스트 케이스 입력 받기
            int n = scanner.nextInt();      // 문서의 개수
            int m = scanner.nextInt();      // 면번째로 인쇄 되었는지 궁굼한 문서의 인덱스( 맨 왼쪽 0 부터 시작)

            Queue<int[]> queue = new LinkedList<>();
            Integer[] importantSort = new Integer[n];       // 중요도를 입력받기 위한 배열

            for(int j=0; j<n; j++){
                int important = scanner.nextInt();          // N개 문서의 중요도

                importantSort[j] = important;
                queue.add(new int[]{j,important});  // {문서인덱스, 중요도}
            }

            Arrays.sort(importantSort,Collections.reverseOrder());      // 중요도 내림차순으로 정렬

            int checkCnt = 0;

            while(true || queue.peek() != null){
                int q[] = queue.poll();

                // 현재 큐와 중요도 비교
                if(importantSort[checkCnt] == q[1] ){
                    checkCnt++;
                    if( q[0] == m  ) {      // 입력받은 문서 인덱스와 현재 큐의 인덱스가 같다면
                        System.out.println(checkCnt);
                        break;
                    }
                }else{      // 현재 큐와 중요도 높은 순위가 일치하지 않으면
                    queue.add(q);
                }
            }
        }
        scanner.close();
    }
}


풀이방법

1. 입력받은 중요도를 배열에 담아 내림차순으로 Sort한다.

2. 입력 받은 큐의 첫번째 값을 가져와 중요도 가장 큰 값과 현재 큐의 중요도를 비교하여 같을 시 다음 중요도 큰 값을 이동 한다.

2.1 이때 입력받은 문서 인덱스와 현재 큐의 인덱스가 같다면 checkCnt를 리턴한다.

3. 현재 중요도 배열의 값과 큐의 중요도 값이 같지 않다면 큐의 첫번째 값을 마지막으로 다시 배치한다.

 

728x90