[BOJ] 1966 프린터큐 - JAVA

1. 문제

---

2. 풀이

생각한 방식은 아래와 같다.
0. idx : 찾으려고 하는 요소의 인덱스. 문서들을 이동할 때마다 매번 바꿔줘야 한다.
order : 지금까지 몇 장 프린트했는지. 맨 앞 문서를 프린트할 때마다 +1한다.
1. 정렬한 nums를 뒤에서부터 돌아가면서 체크한다. (Arrays.sort(nums,Collections.reverseOrder())를 사용하면 앞에서부터 체크해도 된다. 그냥 타입 바꾸기 싫어서 이렇게 했다..)
2. 체크할 때, 해당 nums[i] (이하 num이라 함) 이 queue.peek()과 같아질 때까지 맨 앞 요소를 뒤로 보낸다. 이 때, idx가 0이면 다음 idx는 큐의 사이즈-1가 된다. 0이 아니면 그냥 -1.

3. num==queue.peek()이 되면 프린트하고(poll) order에 +1해준다.
4. 3까지 마무리한 뒤 idx==0이면 내가 알고자 하는 문서가 맨 앞에 와있다는 의미이므로 반복문을 끝낸다.
5. 4에 해당되지 않는다면 num을 바꿔가면서 2~3을 반복한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1966_프린터큐 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());

        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            //입력
            StringTokenizer st = new StringTokenizer(in.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            Queue<Integer> queue = new LinkedList<>();
            int[] nums = new int[N];

            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
                queue.offer(nums[i]);
            }

            Arrays.sort(nums);

            //탐색
            int idx = M;
            int order = 0;
            for (int i = N - 1; i >= 0; i--) {
                while (nums[i] != queue.peek()) {
                    queue.offer(queue.poll());
                    idx = idx == 0 ? queue.size()-1 : --idx;
                }

                queue.poll();
                order++;

                if (idx == 0) {
                    sb.append(order).append("\n");
                    break;
                }else{
                    idx--;
                }
            }
        }
        
        System.out.print(sb);
    }
}

---

3. 결과

알게된 점(전위연산, 후위연산 속도차이)

위에 있던 코드(딱 한줄이었다..)를 무지성으로 복사해서 제출했다가 나중에 코드를 보니 인텔리제이가 친절하게 이 부분을 지적해줬다. 여기 else문에 있는 idx==0? <- 이 부분은 항상 false일거라고..ㅋㅋ 정말 그렇길래 싹 지우고 idx--만 남겨줬다.

if (idx == 0) { 
    sb.append(order).append("\n");
    break;
} else { 
    idx = idx == 0 ? queue.size()-1 : --idx; 
}

그런데 수정한 건 이 부분밖에 없는데 왜 메모리차이가 저렇게 많이 날까 궁금하다.
---> 찾아보니 당연한 결과였다... 후위연산보다 전위연산이 원래 빠르다고 한다. 후위연산은 값을 저장해놓고 그 다음에 +1을 하는데, 전위연산은 그런 거 필요없이 바로 +1한 결과를 리턴해서 메모리와 시간차이가 발생한다.
for문에서 항상 후위연산을 이용했는데 요즘은 컴파일러가 최적화시켜서 반복문에서는 어떤 연산을 사용하든 속도차이가 발생하지 않는다고 한다!