1. 문제

2. 코드

import java.util.*;

public class p1021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Deque<Integer> q = new LinkedList<>();
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int left = 0;
            int right = 0;
            Iterator<Integer> it = q.iterator(); // q에 저장된 요소들을 하나씩 순회
            while (it.hasNext()) {
                int now = it.next();
                left++;
                if (now == x) break;
            }
            right = q.size() - left + 1;
            while (true) {
                if (q.peek() == x) {
                    q.poll();
                    break;
                } else {
                    if (left <= right) {
                        q.offer(q.poll());
                        cnt++;
                    } else {
                        q.offer(q.poll());
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

3. 풀이

• 이 문제는 주어진 N이하의 정렬된 자연수가 담긴 양방향 순환 큐에서 1, 2, 3번 연산을 수행하며 원하는 수를 출력하고, 2번과 3번 연산을 사용한 최소값을 출력하는 문제이다.
• 1번의 원소를 뽑아내는 것은 문제가 되지 않고, 관건은 2번 연산을 하는 것과 3번 연산을 하는 것 중 어떤 것이 이득인지를 계산해야 한다.

• iterator를 사용한 코드와 while문을 사용한 코드의 가장 큰 차이는,
  • iterator를 사용한 코드는 큐의 사이즈를 동적으로 조절하지 않고, 큐의 앞에서부터 하나씩 순차적으로 탐색하여 x 값을 찾아내는 반면에, while문을 사용한 코드는 큐의 사이즈를 동적으로 조절하면서 x 값을 찾아내기 때문이다.
  • iterator를 사용한 코드는 큐의 요소를 순차적으로 탐색하여 x 값을 찾아내기 때문에, 큐의 사이즈가 동적으로 변하지 않는다. 반면에 while문을 사용한 코드에서는 x 값을 찾기 위해 큐의 요소를 앞으로 빼내면서 큐의 사이즈가 계속해서 감소한다. 이 때문에 큐의 메모리 사용량이 크게 증가하여 메모리 초과가 발생할 수 있다.
  • 따라서, while문을 사용한 코드에서도 iterator를 사용한 코드와 같이 큐의 사이즈를 동적으로 조절하지 않는 방법을 사용하면 메모리 초과 문제를 해결할 수 있다. 예를 들어, 큐의 요소를 하나씩 빼내서 x 값을 찾은 뒤, 다시 큐에 추가하는 방법을 사용할 수 있다.

// literator을 사용하지 않은 코드 - > 메모리 초과 발생
import java.util.*;

public class p1021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Deque<Integer> q = new LinkedList<>();
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int left = 0;
            int right = 0;
            while (!q.isEmpty()) {
                int now = q.poll();
                left++;
                if (now == x) break;
                q.offer(now);
            }
            right = q.size() - left + 1;
            while (true) {
                if (q.peek() == x) {
                    q.poll();
                    break;
                } else {
                    if (left <= right) {
                        q.offer(q.poll());
                        cnt++;
                    } else {
                        q.offer(q.poll());
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

4. 링크

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