boj1966

https://github.com/hum02/codingTest/blob/main/baekjoon/boj1966.java

package baekjoon;

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

public class boj1966 {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        int[] answer=new int[T];

        for(int i=0;i<T;i++){
            String[] l1=br.readLine().split(" ");
            String[] l2=br.readLine().split(" ");
            int fileNum=Integer.parseInt(l1[0]);
            int idx=Integer.parseInt(l1[1]);

            Queue<Integer> q= new LinkedList<>();
            for(int j=0;j<fileNum;j++){
                q.add(Integer.parseInt(l2[j]));
            }

            //문서들 우선순위 중 최댓값 알기 위해 int[] arr저장
            int[] arr=new int[l2.length];
            for(int j=0;j<l2.length;j++){
                arr[j]=Integer.parseInt(l2[j]);
            }
            Arrays.sort(arr);

            //q의 peek가 우선순위 가장 높은 것일 때 뽑으면서 순회
            int pollNum=0;
            for(int max_idx=arr.length-1;max_idx>=0;max_idx--){

                while(q.peek()!=arr[max_idx]){
                    q.add(q.poll());

                    //뽑힌 순서 알기 원하는 문서의 위치
                    --idx;
                    if(idx<0){
                        idx=q.size()-1;
                    }
                }

                //q peek의 우선순위가 가장 높은 상태
                //순서 알기 원하던 값이 print되었으면
                if(idx==0){
                    ++pollNum;
                    answer[i]=pollNum;
                    break;
                }

                //원한 문서 말고 다른 문서가 print됨
                q.poll();
                --idx;
                ++pollNum;
            }
        }
        for(int i=0;i<answer.length;i++){
            System.out.println(answer[i]);
        }
    }
}

피드백

• 문제의 핵심은
  -queue를 사용하는 것
  -print되는 문서의 순서를 추적하기 위해 idx를 조정하는 것
  -남은 우선순위 중 최댓값을 찾아내는 것
  인 것 같다.

• 우선 queue의 사용법을 잘 몰라 검색했다. java의 map,queue,list,set.. 등의 collection 사용법을 숙지해야겠다

• 처음에는 idx를 추적하기 위해 (key,value) 와 같은 2개 값을 가진 자료구조를 이용하려 했다. 하지만 이 자료구조를 쓰면서 queue까지 집어넣는
  Queue<Map<Integer,Integer>> 를 이용하는 것은 생각처럼 되지 않았다.
  Map<Integer,Integer>은 key값을 가진 인스턴스 하나가 아니라 map들의 목록이어서 queue에서 꺼내쓰기가 복잡했다. q.SetEntry() 같은 함수로 map인스턴스를 꺼내올 수는 있을 것 같은데 map의 값까지 접근하는 과정이 너무 번잡했다. map을 이용해 푸는 방법도 가능은 할 것 같은데 알아봐야겠다.

+map풀이 추가

map을 이용한 풀이

public class boj1966 {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        int[] answer=new int[T];

        for(int i=0;i<T;i++){
            String[] l1=br.readLine().split(" ");
            String[] l2=br.readLine().split(" ");
            int fileNum=Integer.parseInt(l1[0]);
            int idx=Integer.parseInt(l1[1]);

            Map<Integer,Integer> map= new HashMap<>();
            Queue<Integer> q= new LinkedList<>();
            for(int j=0;j< fileNum;j++){
                map.put(j,Integer.parseInt(l2[j]));
                q.add(j);
            }

            //문서들 우선순위 중 최댓값 알기 위해 int[] arr저장
            int[] arr=new int[l2.length];
            for(int j=0;j<l2.length;j++){
                arr[j]=Integer.parseInt(l2[j]);
            }
            Arrays.sort(arr);

            //q의 peek가 우선순위 가장 높은 것일 때 뽑으면서 순회
            int pollNum=0;
            for(int max_idx=arr.length-1;max_idx>=0;max_idx--){

                while(map.get( q.peek() )!=arr[max_idx]){
                    q.add(q.poll());
                }

                //q peek의 우선순위가 가장 높은 상태
                //순서 알기 원하던 값이 print되었으면
                if( q.peek()==idx ){
                    ++pollNum;
                    answer[i]=pollNum;
                    break;
                }
                //원한 문서 말고 다른 문서가 print됨
                q.poll();
                ++pollNum;
            }
        }
        for(int i=0;i<answer.length;i++){
            System.out.println(answer[i]);
        }
    }
}

• queue에 map<>을 담을 생각만 해서 잘 되지 않았었는데 queue에 index만 담고 map에서 index로 필요할 떄 우선순위를 가져올 생각을 하니 위와 같이 풀 수 있었다. 최고 우선순위이 문서를 찾을 떄마다 map을 조회해야 해서 시간복잡도는 더 안좋은 듯 하나 이 방법이면 추적을 원하는 idx가 여러개일 경우도 답을 찾아낼 수 있어 생각해볼만한 방법인 것 같다.

• 이전에는 문서의 idx를 추적하기 위해 idx변수를 하나 만들어 q가 poll될 때마다 조정하는 방식으로 구현했다. 사실 하나의 문서만 추적하면 되므로 이게 기본적인 방법이었던 것 같은데 위의 자료구조쪽으로만 생각하다보니 이 방법을 빨리 떠올리지 못했다.
  이 방법을 떠올리지 못해서 전체 idx정보를 담은 배열을 새로 만들어야 하나? 그런데 우선순위가 같은 것들은 어떻게 구분하지? 같은 생각이 들면서 복잡해졌었다.