[백준] 1021 회전하는 큐

[문제 링크]

1021번: 회전하는 큐

---

 

 

회전하는 큐는 즉, deque 이다. 

위 문제는 데큐(또는 덱)에 대해서 알고, 명령어만 안다면 쉬운 문제이다.

 

Deque는 스택과 큐의 장점을 합친 자료구조로 양쪽 끝에서 삽입과 삭제 둘 다 가능하다.

 

 

---

 

[해결 코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        LinkedList<Integer> deque = new LinkedList<Integer>();

        int count = 0;

        int N = sc.nextInt(); //큐 크기
        int M = sc.nextInt(); //뽑을 개수

        for(int i = 1; i <= N; i++) {
            deque.add(i);
        }

        int[] num = new int[M];

        for(int i = 0; i < M; i++) {
            num[i] = sc.nextInt(); //뽑을 수 
        }

        for(int i = 0; i < M; i++) {

            int idx = deque.indexOf(num[i]);
            int half_idx;

            if(deque.size() % 2 ==0) {
                half_idx = deque.size() / 2 - 1;
            }
            else {
                half_idx = deque.size() / 2;
            }


            if(idx <= half_idx) {   //덱 왼쪽 이동
                for(int j = 0; j < idx; j++) {
                    int temp = deque.pollFirst();
                    deque.offerLast(temp);
                    count++;
                }
            }
            else{  // 덱 오른쪽 이동
                for(int j = 0; j < deque.size() - idx; j++) {
                    int temp = deque.pollLast();
                    deque.offerFirst(temp);
                    count++;
                }
            }
            deque.pollFirst(); //이동 후 삭제
        }

        System.out.println(count);

    }
}

 

코드에 대해 설명하자면 2번(왼쪽 이동), 3번(오른쪽 이동)의 수를 합친 값을 출력하면 되는데, 

뽑아야 할 숫자의 index를 idx로 지정하고 전체 데큐가 짝수이면 전체 나누기 2 - 1을 하고, 홀수이면 전체 나누기 2를 한다.

이유는 뽑아야 할 숫자를 뽑기 위해 왼쪽으로 이동할 것인지, 오른쪽으로 이동할 것인지 선택하기 위함이다.

 

왼쪽 이동의 경우, 데큐의 반의 값과 비교했을 때 뽑아야 할 수가 작아야한다.

뽑을 수가 작을 때, 왼쪽으로 이동을 해야하므로 데큐의 앞쪽 값을 제거하고 그 수를 데큐의 가장 뒤에 추가한다. 

이때 2번을 수행한 것이므로 카운트를 해줘야한다.

 

오른쪽 이동은 왼쪽과 반대로 하면 된다. 

오른쪽 이동은 즉, 데큐의 반의 값과 비교했을 때 뽑아야 할 수가 크다는 것이고,

오른쪽 이동을 해야하므로 데큐의 맨 뒤의 값을 제거하고 그 수를 데큐의 맨 앞에 추가한다. 

이때는 3번을 수행한 것이므로 카운트를 한다.

 

왼쪽과 오른쪽 이동을 마치고 뽑아야 할 수가 됐다면 그 값을 삭제하면 끝이다.

 

 

 

---

 

 

위 문제를 제출하기 전 검사를 했을 땐, 정답이 맞게 나왔다. 하지만 제출을 하면 계속 틀렸다. 그 이유에 대해 고민하다 add()를 offer()로, remove()를 poll()로 고쳐서 제출하니 정답으로 인정했다. 

 

add()와 offer()의 차이를 검색해보았다.

offer()는 실패시 false를 반환하지만, add()는 throw를 던진다.

 

아마.. add()로 하면 예외를 던져서 그런거 같은데.. 왜 안되는지는 아직 잘모르겠다..