[BOJ] 1966 - 프린터큐 (Java)

알고리즘

• 구현

• 자료 구조

• 시뮬레이션

• 큐

1. 문제

2. Idea

• 입력으로 받은 문서들, 문서의 위치, 중요도를 큐에 저장

• 큐를 순회하면서 현재 문서의 중요도보다 높은 중요도를 가진 문서가 큐에 있는지 확인하여 중요도가 높은 문서를 먼저 출력

3. 풀이

3.1. 입력값 처리 및 cnt 초기화

• for문으로 각 테스트 케이스 처리

• T: 문서의 개수(a), 문서의 위치(b)로 구성

for (int i = 0; i < T; i++) {
	int a = sc.nextInt();
	int b = sc.nextInt();
	int cnt = 0;
    ...
}

3.2. 큐 생성 및 저장

• q: [문서 위치, 중요도]로 구성

Queue<int[]> q = new LinkedList<>();
for (int j = 0; j < a; j++) {
q.add(new int[]{j, sc.nextInt()});
}

3.3. while문 반복

• while문을 통해 문서를 처리 큐에서 하나의 문서를 꺼내고(present), 이 문서의 중요도와 큐에 남아있는 문서들의 중요도 비교

while (true) {
	int[] present = q.remove();
    ...
}

3.4. 중요도 비교

• 현재 문서의 중요도(present[1])보다 큐에 남아있는 다른 문서들의 중요도가 더 높은 경우(queue[1] > present[1]), 현재 문서를 큐의 뒤로 이동하여 나중에 다시 처리

for (int[] queue : q) {
	if (queue[1] > present[1]) {
		tf = false;
		break;
	}
}

3.5. 인쇄 가능 여부 확인

• 중요도가 높은 문서를 먼저 처리하기 위해 사용하여 현재 문서가 인쇄될 수 있는지 여부 확인(tf)

• tf==true: 현재 문서를 출력 (cnt++), 요청한 문서의 위치와 비교하여 요청한 문서가 출력되었는지 확인

if (tf) {
	cnt++;
	if (present[0] == b){break;}
	} else {q.add(present);}
}

3.6. 결과 출력

System.out.println(cnt);

4. 전체코드

import java.util.*;
public class BOJ_1966 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(String.valueOf(sc.nextLine()));

        for (int i = 0; i < T; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int cnt = 0;
            Queue<int[]> q = new LinkedList<>();
            for (int j = 0; j < a; j++) {
                q.add(new int[]{j, sc.nextInt()});
            }

            while (true) {
                int[] present = q.remove();
                boolean tf = true;

                for (int[] queue : q) {
                    if (queue[1] > present[1]) {
                        tf = false;
                        break;
                    }
                }

                if (tf) {
                    cnt++;
                    if (present[0] == b){break;}
                } else {q.add(present);}
            }
            System.out.println(cnt);
        }
    }
}