[알고리즘 / 백준] 1966 - 프린터 큐

문제는 위와 같고 (우선순위, 인덱스) 형태의 튜플을 리스트로 저장한 뒤, 앞에서부터 차례대로 꺼내서 우선순위가 최대인지 확인합니다. 우선 순위가 최대라면 먼저 출력 count 를 1 추가한 뒤, 원래 뽑으려고 한 인덱스가 맞는지 확인하여 맞다면 그대로 출력 count 를 프린트하고 종료합니다. 아니라면 그냥 pop(0) 합니다. 맨 앞에서 꺼낸 데이터의 우선순위가 최대가 아니라면 해당 데이터를 다시 리스트의 젤 마지막에 추가합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

test_case = int(stdin.readline())

for _ in range(test_case):
    n, m = map(int, stdin.readline().split())
    queue = list(map(int, stdin.readline().split()))
    queue = [(i, idx) for idx, i in enumerate(queue)]  # [(우선 순위, 인덱스), ...] 형태의 리스트로 변환

    count = 0
    while True:
        # queue 의 가장 앞에 있는 값이 우선 순위가 최대인 값인 경우
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            # 그 값이 찾고 있는 인덱스의 값이라면
            if queue[0][1] == m:
                print(count)
                break
            else:
                queue.pop(0)  # 찾는 값이 아닌 경우 그냥 pop (프린트)
        else:
            queue.append(queue.pop(0))  # 우선 순위가 최대가 아닌 경우는 pop 하고 다시 push 하기

 

자바 코드는 다음과 같습니다. 파이썬 코드에서 사용한 로직과 최대한 비슷하게 구현하기 위해 아래와 같이 List 를 사용하였는데 제공되는 Queue 인터페이스를 쓰는 것도 좋은 방법이 될 것 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCase; i++) {
            int[] nm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            List<int[]> queue = new ArrayList();

            int[] priority = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int index = 0; index < nm[0]; index++) {
                int[] tmp = new int[2];
                tmp[0] = priority[index];
                tmp[1] = index;
                queue.add(tmp);
            }

            int count = 0;
            while (true) {
                if (queue.get(0)[0] == queue.stream().max((a, b) -> a[0] - b[0]).orElse(new int[1])[0]) {
                    count++;
                    if (queue.get(0)[1] == nm[1]) {
                        System.out.println(count);
                        break;
                    } else {
                        queue.remove(0);
                    }
                } else {
                    queue.add(queue.remove(0));
                }
            }
        }
    }
}