문제 링크

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

풀이

  • 양방향 순환 큐이기 때문에 덱(Deque, ArrayDeque)을 사용하려 했으나, 연결 리스트(LinkedList)로도 구현이 가능하다는 스터디 팀원의 설명을 듣고 연결 리스트로 구현해보았다.
  • 첫 번째 원소를 뽑아내는 1번 연산은 결과값 result에 포함하지 않는다. 오직 2번, 3번 연산만 포함한다.
  • 뽑고자 하는 원소가 어느 위치에 있는지 확인 후, 첫 번째 원소로부터 더 가까운 방향으로 원소들을 이동시킨다. LinkedList에도 indexOf() 메소드가 있기 때문에 위치(인덱스)를 쉽게 얻을 수 있다.
    • 첫 번째 원소로부터 오른쪽 거리를 indexOf()로 구하고, 전체 원소 개수에서 오른쪽 거리를 빼면 왼쪽 거리를 구할 수 있다.
    • 거리가 더 가까운 방향을 정한 후 뽑고자 하는 원소가 첫 번째 원소로 올 때까지 offer와 poll을 반복한다. 여기서는 양방향 큐이므로 offerFirst(), offerLast(), pollFirst(), pollLast()를 사용한다.
  • 뽑고 싶은 원소에 다다르면 해당 원소를 뽑고, result에 왼쪽 혹은 오른쪽으로 이동한 거리를 더한다. 이제 뽑아낼 수의 개수 m만큼 반복하면 원하는 값을 구할 수 있다.
소스 코드 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 큐 초기화 (연결 리스트 사용)
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) queue.offerLast(i);
        
        st = new StringTokenizer(br.readLine());
        int result = 0;
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            
            if (queue.peekFirst() == target) {
                // 첫 번째 원소가 뽑아낼 수일 경우
                queue.pollFirst();
            } else {
                // 왼쪽과 오른쪽 중 더 짧은 거리를 이동
                int rightDist = queue.indexOf(target);
                int leftDist = queue.size() - rightDist;
                
                if (leftDist < rightDist) {
                    while (queue.peekFirst() != target) {
                        queue.offerFirst(queue.pollLast());
                    }
                    // 첫 번째 원소 추출
                    queue.pollFirst();
                    result += leftDist;
                } else {
                    while (queue.peekFirst() != target) {
                        queue.offerLast(queue.pollFirst());
                    }
                    // 첫 번째 원소 추출
                    queue.pollFirst();
                    result += rightDist;
                }
            }
        }
        
        System.out.println(result);
        br.close();
    }
}