[백준] no1944: 프린터 큐

문제

: 대기열에서 중요도 우선으로 요소 쳐내기

: 다른 더 높은 중요도를 가진 요소가 있다면, 그 전에 나온 애는 다시 대기열 맨뒤로 보내기

: 같은 중요도가 있을 수 있음

 

문제 링크 : https://www.acmicpc.net/problem/1966

---

원리

1. 대기열에 [식별자, 중요도]로 지정해서 줄세움

2. 중요도를 받아서 내림차순 정렬

3. 목표 식별자를 미리 받아둠(Input으로 들어오는 위치에 해당하는 식별자)

4. 중요도 순으로 식별자를 쳐내고, 쳐낼때마다 count + 1

5. 목표 식별자에 도달하면 count 출력

 

---

풀이방법

1. ArrayList : 중요도를 받아서 내림차순 정렬

2. Deque : 대기열. 요소는 [식별자, 중요도]로 되어있는 int형 배열

3. count : 뽑혀나온 순서값. 첫 번째부터 시작

4. goal : 목표 식별자

---

나의 코드

1. Deque(대기열) + ArrayList(중요도 순서) + HashMap(각 수별 중요도)

: 메모리가 미침 + 시간초과 + 이상하게 토크나이저에서 멈춤(결과는 또 나옴)

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

public class no1966 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            int num = Integer.parseInt(st.nextToken());
            int loc = Integer.parseInt(st.nextToken());
            int goal = 0;
            int result = 1;  // 뽑아내진 순서로써 첫번째부터 시작

            Deque<Integer> dq = new ArrayDeque<>(); // 대기열
            HashMap<Integer, Integer> map = new HashMap<>(); // (값, 중요도)
            List<Integer> list = new ArrayList<>();  // 중요도 순서

            for (int j = 0; j < num; j++) {
                dq.add(j);
                int important = Integer.parseInt(st2.nextToken());
                map.put(j, important);
                list.add(important);
                if (loc == j) goal = j; // 주어진 인덱스에 있는 목표 값
            }

            Collections.sort(list, Collections.reverseOrder()); // 중요도 순서대로 정렬

            while (true) {
                if (map.get(dq.peek()) == list.get(0)) {  // 리스트의 맨앞 숫자가 대기열의 숫자에 해당하는 중요도로 같을경우
                    if (dq.pollFirst() == goal) {         // 대기열의 숫자와 목표 숫자가 같을 경우
                        bw.write("" + result + "\n");
                        break;
                    }
                    // 우선순위만 같고 목표 숫자랑은 다를 경우, 제거하고 count + 1
                    list.remove(0);
                    dq.poll();
                    result++;

                } else {
                    dq.addLast(dq.pollFirst()); // 현재 뽑은 수가 중요도가 같지 않은 경우, 대기열 맨뒤로 다시 보냄
                }
            }
        }

        bw.close();
    }
}

 

2. ArrayList(중요도 순서대로 순번) + Deque(순서+중요도로 된 배열의 대기열)

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

public class no1966 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

            int num = Integer.parseInt(st.nextToken());
            int location = Integer.parseInt(st.nextToken());
            Deque<int[]> dq = new ArrayDeque<>();
            ArrayList<Integer> list = new ArrayList<>();
            int goal = 0;
            int count = 1;

            for (int j = 1; j <= num; j++) {
                int temp = Integer.parseInt(st2.nextToken());
                dq.add(new int[]{j, temp});
                list.add(temp);
                if (j == location+1) goal = j;
            }

            Collections.sort(list, Collections.reverseOrder());

            while(!list.isEmpty()) {
                if ((dq.peek()[1] == list.get(0)) && dq.peek()[0] == goal) {
                    bw.write(""+count+"\n");
                    break;
                } else if (dq.peek()[1] == list.get(0)) {
                    list.remove(0);
                    dq.poll();
                    count++;
                } else {
                    dq.add(dq.poll());
                }
            }
        }

        bw.close();
    }
}