알고리즘 풀이(JAVA) - 백준 알고리즘_1966(프린터 큐)

By on November 4, 2019

문제

문제 링크 : https://www.acmicpc.net/problem/1966

프린터 큐 문제

풀이

  • Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만) 이 무엇을 의미 하는지 이해하는데 한참이 걸렸다.

    • M 은 예제로 주어진 우선순위 문서의 위치 값을 나타낸다.

      • 예) 1 1 9 1 1 1 우선순의에서 M : 0 을 주었때에 가장 첫번째 있는 1을 말하는 것이다.

        • 입력 : 1 1 9 1 1 1
        • 1차 회전 : 1 9 1 1 1 1
        • 2차 회전 : 9 1 1 1 1 1
        • 3차 : 우선순위 정리가완료 되었으므로 0번째 있는 문서는 5번째로 출력 된다.

  • 우선 큐를 2개 선언 하였다.

    • 정렬 되지 않은 docsQ, 출력 해야할 printQ
    • 큐는 처음에 확인 하고자 하는 M 번째 문서를 표기 하기 위해 mark 를 하였다. (int[] {우선순위, mark})

  • 큐의 첫번째 데이터를 뽑아서 나머지 큐 에서 자신보다 우선순위가 높은 문서가 있는지 체크 한다(checkQ(int[] chk, Queue<int[]> chkQ))

    • 우선순위가 큰 문서가 없을 경우 printQ 로 입력한다.
    • 우선순위가 큰 문서가 있을 경우 docsQ 의 제일 마지막으로 입력한다.

  • printQ 에서 mark 가 되어있는 문서의 위치를 출력한다.(showResult())

소스

  • 프린터 큐(1966)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjooin_1966 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int caseCnt = Integer.parseInt(reader.readLine());
		
		for(int i = 0; i < caseCnt; i++) {
			String[] qPos = reader.readLine().split(" ");
			String[] docs = reader.readLine().split(" ");
			
			int docLen = Integer.parseInt(qPos[0]);
			int printNum = Integer.parseInt(qPos[1]);
			
			Queue<int[]> printQ = print(docLen, docs, printNum);
			showResult(printQ, docLen);
		}
	}

	
	private static void showResult(Queue<int[]> printQ, int docLen) {
		for(int i = 1; i <= docLen; i++) {
			int[] doc = printQ.poll();
			if(doc[1] == 1) {
				System.out.println(i);
				break;
			}
		}
	}
	
	private static Queue<int[]> print(int docLen, String[] docs, int printNum) {
		Queue<int[]> printQ = new LinkedList<int[]>();
		Queue<int[]> docsQ = makeDocsQ(docLen, docs, printNum);
		
		while(true) {
			if(docsQ.size() == 0 ) break;
			int[] doc = docsQ.poll();
			if(checkQ(doc, docsQ)) {
				docsQ.add(doc);
			}else {
				printQ.add(doc);
			}
		}
		return printQ;
	}
	
	private static boolean checkQ(int[] chk, Queue<int[]> chkQ) {
		int len = chkQ.size();
		Queue<int[]> queue = new LinkedList<int[]>(chkQ);
		for(int i = 0; i < len; i++) {
			int[] tmp = queue.poll();
			if(tmp[0] > chk[0] ) {
				return true;
			}
		}
		return false;
	}

	private static Queue<int[]> makeDocsQ(int docLen, String[] docs, int printNum) {
		int mark = 0;
		Queue<int[]> docsQ = new LinkedList<int[]>();
		for(int i = 0; i < docLen; i++) {
			if(i == printNum)
				mark = 1;
			else
				mark = 0;
			docsQ.add(new int[]{Integer.parseInt(docs[i]), mark});
		}
		return docsQ;
	}
}

Back to blog