[백준] 단계별로 풀어보기(단계:19,큐/덱,JAVA)1966번, 프린터 큐

문제 링크

1966번: 프린터 큐

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 큐는 FIFO(선입선출)의 자료구조를 가지고 있습니다.

FIFO는 먼저 들어간 데이터들이 출력할 때 먼저 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 큐에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 3을 큐에 넣었을 때

3

2. 2을 큐에 넣었을 때

3

2

3. 1을 큐에 넣었을 때

3

2

1

4. 큐에 하나의 자료를 출력하라는 명령이 떨어졌을 때

3

2

1

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

1

위에 표를 보면 가장 먼저 저장된 데이터가 먼저 출력되는 것을 볼 수 있듯이 큐는 FIFO형태의 자료구조입니다.

Java에서 큐를 표현하려면 LinkList<>()로 선언해주어야 하므로 큐를 선언해주었습니다.

문제에서 살펴보면 알고리즘을 발견할 수 있습니다.

1. 큐에 저장된 값부터 중요도가 가장 높은 것을 찾습니다.

2. 중요도가 가장 높은 값을 큐에 맨 앞으로 옮기고 앞에 값들은 뒤로 넘깁니다.

3. 중요도가 가장 높은 값을 poll()을 진행합니다.

4. poll()한 값이 입력값에서 찾는 값과 같다면 빠진 순서를 결과로 출력하고 틀리면 위 과정을 반복합니다.

예제 입력1에 2번째 제공된 예제에 적용해보면

N = 4, M = 2

중요도 = 1 2 3 4

1. 가장 중요도가 높은 것을 찾습니다.

문서 번호	0	1	2	3
중요도	1	2	3	4

2. 중요도가 가장 높은 값을 큐에 맨앞에 옯기고 앞에 값들을 뒤로 넘긴다.

문서번호	3	0	1	2
중요도	4	1	2	3

3. 큐에 맨 앞에 있는 값을 나오게하는 poll()을 진행합니다.

문서번호	0	1	2
중요도	1	2	3

queue.poll() = 3

4. 입력값과 M과 같은지 확인한다. 3 != 2 이므로 다르기 때문에 위 과정을 반복한다.

5. 가장 중요도가 높은 것을 찾습니다.

문서번호	0	1	2
중요도	1	2	3

6. 중요도가 가장 높은 값을 큐에 맨앞에 옮기고 앞에 값들을 뒤로 넘긴다.

문서번호	2	0	1
중요도	3	1	2

7. 큐에 맨 앞에 있는 값을 나오게하는 poll()을 진행합니다.

문서번호	0	1
중요도	1	2

queue.poll() = 2

8. 입력값과 M과 같은지 확인한다. 2 == 2 이 같으므로 2번째에 빠졌으므로 결과 2를 출력합니다.

결과 = 2

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 중요도와 N과 M을 저장하였습니다.
• 반복문을 통해서 큐에 번호와 중요도 저장 배열을 초기화하였습니다.
• 프린터 입력값 출력 순서를 구하는 함수 printQueue를 만들었습니다.
• System.out.println에 StringBuilder에 저장된 결과를 출력하였습니다.

• printQueue에서는 위에 설명한 알고리즘을 반복하고 있습니다.
• 큐에 최대값을 찾을 때 poll()과 offer()을 반복하여 큐에 저장된 인덱스를 이용하여 최대값을 구하였습니다.
• 최대값을 구하였으면 그 앞에까지 poll(), offer()을 진행하여 최대값이 peek()가 될 수 있게 하였습니다.
• 최대값이 peek()가 되었으므로 poll()을 진행하여 입력값과 같은지 확인하고 같으면 현재 순서 result를 StringBuilder에 저장하고 아니면 위에 방법을 반복하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Queue<Integer> queue = new LinkedList<>();	//순서 저장 큐
	static StringBuilder sb = new StringBuilder();	//결과 저장 StringBuilder
	static int[] arr;		//중요도 저장 배열
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력 값을 받는 BufferedReader
        //---------입력값 저장 및 큐와 함수 초기화----------
		int index = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int i=0;i<index;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			arr = new int[N];
			st = new StringTokenizer(br.readLine());
            		//큐, 배열 저장
			for(int j=0;j<N;j++) {
				arr[j] = Integer.parseInt(st.nextToken());
				queue.offer(j);
			}
            
			printQueue(N,M);	//함수 실행
			queue.clear();	//큐 초기화
		}
		System.out.println(sb.toString());
		br.close();
	}
    	//---------프린터 큐 순서 구하는 함수---------
	public static void printQueue(int N, int M) {
		int result = 1;	 //결과값
		int check = N;	//몇 번째 반복인지 확인
		for(int i=0;i<N;i++) {
			int index=0;
			int temp = queue.poll();
			int max = arr[temp];
			queue.offer(temp);
            		//중요도 최대값 찾기
			for(int j=1;j<check;j++) {
				temp = queue.poll();
				queue.offer(temp);
				if(arr[temp]>max) {
					index=j;
					max = arr[temp];
				}
			}
           		//최대값 앞 만큼 poll, offer 진행
			for(int j=0;j<index;j++) {
				temp = queue.poll();
				queue.offer(temp);
			}
			temp = queue.poll();	//큐에 나오는 값
            		//나온 값과 순서를 찾는 값이 같은 경우
			if(temp==M) {
				sb.append(result + "\n");
				break;
			}
			check--;
			result++;
		}
	}
}