이것저것 개발 블로그

https://www.acmicpc.net/problem/1966

풀이)

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

public class Main_BJ_1966_프린터큐 {
    static class node{
        int loc;
        int w;

        public node(int loc, int w){
            this.loc = loc;
            this.w = w;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc = 0; tc<t; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n =  Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            LinkedList<node> q = new LinkedList<>();

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                q.offer(new node(i, Integer.parseInt(st.nextToken())));
            }

            int cnt = 0;
            while(!q.isEmpty()){
                node cur = q.poll();
                boolean isMax = true;

                for(int i=0; i<q.size(); i++){
                    if(cur.w < q.get(i).w){
                        q.offer(cur);
                        for(int j=0; j<i; j++)
                            q.offer(q.poll());

                        isMax = false;
                        break;
                    }
                }

                if(!isMax)
                    continue;

                cnt++;
                if(cur.loc == m)
                    break;
            }//while
            System.out.println(cnt);
        }//tc
    }//main
}

큐를 정말 queue로 사용하기보다 linkedlist를 이용해서 구현했다.

이 점을 이용하면 큐 안에 있는 중요도를 볼 수 있어서 편리하다.

현재 중요도보다 큰 애를 발견하면 그 애부터 중요도보다 큰 애 전까지를 큐에 삽입한다.

처음 나온 원소가 가장 큰 경우는 해당 원소의 첫 위치가 m과 같은지를 비교해야 한다.

만약 큐에서 나온 원소보다 중요도가 큰 원소가 있는 경우, 그 원소 앞에 있던 원소들을 뒤로 보내야 한다.

그리고 다시 첫 원소를 빼낸 후 큐에 다시 삽입된 원소보다 중요도가 큰 원소가 있는지 검사해야 한다.

따라서 플래그를 설정해 하는게 편하다!

쉬운 구현 문제인데 고민이 좀 많았다...