[코드트리 조별과제] 수 선택 순서 (우선순위 큐)

수 선택 순서 문제 링크

코드트리에서 위의 문제를 푼 과정을 기록해보도록 하겠습니다!

문제는 우선순위 큐 문제였습니다!

코드 Flow는 다음과 같습니다.
1. int[]를 담는 Queue 생성

• 0번 인덱스 : 값, 1번 인덱스 : 초기의 인덱스

2. 초기 큐의 값들을 담는 Priority Queue(우선순위 큐) 생성
3. while 문을 돌면서 문제 조건에 맞으면 queue, priority queue poll, cnt++

이 문제는 초기에 주어지는 인덱스의 값이 몇 번째에 queue에서 poll되는지 구하는 문제입니다.
따라서, Queue의 타입을 값과 초기 인덱스를 담는 int[]로 담아서
이후에 queue에서 꺼내서 비교할 때 다음 2가지를 비교했습니다.
1. 해당 값과 초기 인덱스에 해당하는 값이 같은지(int[0])
2. 초기 인덱스와 구할 인덱스가 같은지(int[1])

위의 과정으로 구현했습니다!
전체 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(input.nextToken());
        int targetIdx = Integer.parseInt(input.nextToken());
        int target = 0;

        // num, idx
        Queue<int[]> queue = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        StringTokenizer queueInput = new StringTokenizer(br.readLine());        
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(queueInput.nextToken());
            queue.add(new int[]{num, i});
            pq.add(num);

            if (targetIdx == i) {
                target = num;
            }
        }

        int cnt = 0;
        while (true) {

            int[] head = queue.peek();
            int pqHead = pq.peek();

            if (head[0] == pqHead) {
                queue.poll();
                pq.poll();
                cnt++;
                if (head[0] == target && head[1] == targetIdx) {
                    System.out.println(cnt);
                    break;
                }
            } else {
                int[] nums = queue.poll();
                queue.add(nums);
            }

        }
    }
}