[24/11/07] 큐

1966

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

// The main method must be in a class named "Main".
//2초면 2억번... N은 100, 100* 100 0000 00 / 100만까지
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(bf.readLine());
        PriorityQueue<O> queue = new PriorityQueue<>(new OComparator());
        for(int i=0; i<testCase; i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int N = Integer.parseInt(st.nextToken());
            int location = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(bf.readLine());
            for(int j=0; j<N; j++){
                int pNow = Integer.parseInt(st.nextToken());
                if(j==location){
                    O o = new O(pNow,true);
                    queue.add(o);
                }
                else{
                    O o = new O(pNow,false);
                    queue.add(o);
                }
            }
            int count =1;
            while(!queue.isEmpty()){
                O o = queue.poll();
                if(o.isFind && (queue.isEmpty() || !queue.peek().isFind)){ //같은 우선순위가 있을때 마지막 출력
                    System.out.printf("%d\n",count);
                    break;
                }
                else{
                    count++;
                }
            }
        }
        
    
    }
}
    class O {
        public int p;
        public boolean isFind;
        public O(int p , boolean flag){
            this.p=p;
            this.isFind = flag;
        }
    }
    
    class OComparator implements Comparator<O>{
    //우선순위 높은거부터 출력 >> 내림차순
        public int compare(O o1 , O o2){
            if(o1.p==o2.p){
                
            }
            return o2.p - o1.p; 
        }
    }

위 코드는 우선순위 큐로 풀다가 동일 우선순위일 경우 큐 rear로 보내야되는데 그건 우선순위 큐로 어케 할수가 없겠어서 하다가 포기한 풀이이다.

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

// The main method must be in a class named "Main".
//2초면 2억번... N은 100, 100* 100 0000 00 / 100만까지
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(bf.readLine());
        for(int i=0; i<testCase; i++){
            Queue<O> queue = new LinkedList<>();
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int N = Integer.parseInt(st.nextToken());
            int anslocation = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(bf.readLine());
            int locationNow = 0;
            Integer[] priorityArr = new Integer[N];
            for(int j=0; j<N; j++){
                int pNow = Integer.parseInt(st.nextToken());
                priorityArr[j]=pNow;
                O o = new O(pNow,locationNow++);
                queue.add(o);
            }
            Arrays.sort(priorityArr,Collections.reverseOrder());
            int count =1;
            int index=0;
            while(!queue.isEmpty()){
                O o = queue.poll();
                if(o.p==priorityArr[index] && o.location==anslocation){
                    System.out.printf("%d\n",count);
                    break;
                }
                else if(o.p==priorityArr[index] && o.location!=anslocation){
                    count++;
                    index++;
                }
                else if(o.p!=priorityArr[index]){
                    queue.add(o);
                }
            }
        }
        
    
    }
}
    class O {
        public int p;
        public int location;
        public O(int p , int location){
            this.p=p;
            this.location = location;
        }
    }

이게 정답 풀이인데 꽤 돌아푼거같다. 

결국 우선순위를 모두 배열에 저장하고 있어야해서 우선순위 배열을 따로 만들어서 내림차순한 이후에 

현재 front쪽에서 poll 한게 최대 우선순위는 맞는데 찾고자 하는 위치는 아닐때 우선순위 배열에서 다음 원소를 참조하여 다음으로 큰 우선순위를 가져온다. 

 

우선순위 처리를 어떻게 했나 궁금해서 다른 풀이 보니까 그냥 poll해서 하나씩 큐에서 비교하면서 얘가 최소인가 봤다.

이러면 또 각 실행 안에서 순회하면서 비교하는 O(N)이 또 들어가서 그냥 O(1) 걸리는 배열 따로 만드는게 더 좋은거같다.