[Algorithm Study] 백준 1966

문제 출처 : https://www.acmicpc.net/problem/1966

문제 정리

1. 주어진 문서에 대해서 중요도를 파악한다.
2. 문제에서 원하는 문서의 출력 순서를 파악하여 정답으로 출력한다.

위의 문제를 해결하는데 있어서 핵심으로 활용한 방안은 배열이 주어졌을 때 원형 링크드 리스트 처럼 작동하기 위해 반복문을 활용한 것이 핵심입니다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

        int T = Integer.parseInt(br.readLine());
        int[] answers = new int[T];
        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int[][] map = new int[N][2];
            PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int value = Integer.parseInt(st.nextToken());
                queue.add(value);
                if(j == M){
                    map[j][0] = value;
                    map[j][1] = 1;
                }
                else{
                    map[j][0] = value;
                    map[j][1] = 0;
                }
            }
            int cnt = 0;
            boolean logic = true;
            int start = 0;
            while(logic){
                int check = queue.poll();
                cnt++;
                //마치 원형 링크드 리스트 처럼 작동
                for(int j = start; j < N+start; j++){
                    if(map[j % N][0] == check){
                        if(map[j % N][1] == 1){
                            logic = false;
                        }
                        start = j+1;
                        break;
                    }
                }
            }
            answers[i] = cnt;
        }
        for(int answer : answers){
            System.out.println(answer);
        }
    }
}