[Java] 1021번. 회전하는 큐

1. 문제 분석

초기화된 큐에서 특정한 수를 차례대로 뽑아내기 위해 총 몇번의 큐를 움직여야 하는가에 대한 문제이다.

 

우리는 큐에서 특정한 값을 뽑아내기 위해서 딱 세가지 행동만 할 수 있다.

(1) 첫 번째 원소를 뽑아 낸다.

(2) 왼쪽으로 한 칸 씩 이동시키고, 가장 앞에 있는 수는 가장 뒤로 이동시킨다.

(3) 오른쪽으로 한 칸 씩 이동시키고, 가장 뒤에 있는 수는 가장 앞으로 이동시킨다.

 

이 때 문제에서 2,3번 행동을 몇번 했는가를 계산해야 한다.

 

백준 문제에서 제시한 예제를 보자.

 

예제 1)

큐의 크기는 10이고 3개의 수를 뽑아내려고 하는데, 이 때 1,2,3을 뽑아내고자 한다.

 

가장 위에 줄에서 보면 크기 10인 큐를 1-10으로 초기화 한다.

1이 가장 앞에 있는 상태이므로 1을 뽑기 위해서는 1번 행동을 하면 된다.

1번 행동을 진행하면 큐는 2-10이 된다.

 

2가 가장 앞에 있으므로 2를 뽑기 위해서는 1번 행동을 하면 된다.

1번 행동을 진행하면 큐는 3-10이 된다. 

 

3이 가장 앞에 있으므로 3을 뽑기 위해서는 1번 행동을 하면 된다.

1번 행동을 진행하면 큐는 4-10이 되고 목표한 수를 모두 뽑기 완료한다.

 

따라서 이 문제에서 1번 행동을 3번 하면 모든 수를 뽑을 수 있었고, 2,3번 행동은 하지 않았으므로 결과값은 0이 된다.

 

예제 2)

매우 쉬웠던 1번 예제와 달리 2번은 꽤나 복잡하다.

예제 2에서는 큐의 크기는 10이고 3개의 수 2, 9, 5 를 뽑아내고자 한다.

 

복잡하니까 번호를 붙여 차례대로 살펴보자

(1) 크기가 10인 큐를 1~10의 수로 초기화 한다.

(2) '2'를 뽑기 위해서 '2'가 가장 앞에 위치해야 하므로 2번 행동을 통해 큐를 왼쪽으로 한 칸 이동시킨다. 

(3) '9'를 뽑기 위해서 '9'가 가장 앞에 위치해야 하므로 3번 행동을 세 번 해서 오른쪽으로 세 칸 이동시킨다.

(4) '5'를 뽑기 위해서 '5'가 가장 앞에 위치해야 하므로 3번 행동을 네 번 해서 오른쪽으로 네 칸 이동시킨다.

 

위 그림을 차근차근 따라해보면 이해가 될 것이다.

이해가 끝나면 다음 문제에 대해 생각해보아야 한다.

(1) 어떤 자료구조를 활용 할 것인가?

(2) 계산을 통해서 오른쪽으로 이동할 지를 어떻게 결정할 것인가?

 

위 두 문제에 대한 나의 해답은 다음과 같다.

 

(1) 어떤 자료구조를 활용할 것인가?

왼쪽으로 이동하면 가장 앞의 요소가 제거되고, 가장 뒤에서는 제거한 요소를 삽입한다.

또한 오른쪽으로 이동하면 가장 뒤의 요소가 제거되고, 가장 앞에 제거된 요소가 삽입된다.

즉, 배열의 가장 앞 뒤에서만 삽입/제거가 일어나는 구조이므로 Deque가 적절하다.

 

(2) 계산을 통해서 오른쪽으로 이동할 지를 어떻게 결정할 것인가?

우리는 딱 보면 어느 쪽으로 이동해야 빨리 도착하는지 볼 수 있다.

하지만 컴퓨터는 우리가 알려주지 않으면 모른다. 따라서 우리가 컴퓨터에게 방향을 지정해야 한다.

 

배열의 중간 지점을 중심으로 생각해보면,

앞부분에 위치한 수를 찾기 위해서는 2번 행동을 해서 전체적으로 왼쪽으로 돌리는 것이 좋고

뒷부분에 위치한 수를 찾기 위해서는 3번 행동을 해서 전체적으로 오른쪽으로 돌리는 것이 좋다.

 

위 사진에서 현재 배열의 크기가 9이기 때문에 (int)9 / (int)2 = 4로 계산해서

인덱스가 4번일 때 까지는 2번 행동을, 그 이상일 때는 3번 행동을 한다.

 

따라서 찾으려는 수의 인덱스를 통해서 방향을 결정할 수 있다.

 

그러나 우리는 이 문제를 Deque로 풀기로 하였고,

Deque의 구조 상 가장 앞 요소와 가장 뒤 요소를 제외하고는 추가/접근/삭제가 불가능하다.

직접 이동을 해야지 요소의 위치를 알 수 있다.

 

그래서 추가적인 방법이 필요했다.

이 문제는 배열이지만, '회전'의 개념과 가깝다. 1바퀴를 돌면 원래의 수로 돌아온다.

그렇다면 한 방향으로 배열의 크기만큼 이동하면 원래의 수로 돌아온다.

 

위 그림을 보면 3번 행동 3번을 통해서 요소를 뽑을 수 있지만,

2번 행동을 6번 해서도 요소를 뽑을 수 있다.

그리고, 3번 행동과 2번 행동의 합은 무조건 Deque의 사이즈이다.

 

그렇게 되면 무조건 일단 한 방향으로 이동하고

이 때 카운트 한 값이 배열의 중간보다 크면 요소가 중간보다 뒤 쪽에 위치했다는 의미이고

전체 배열에서 카운트 값을 빼면 반대 방향으로 갔을 때 움직인 횟수를 계산할 수 있다.

 

2. 구현

사용할 주요 변수

deque : 숫자 배열을 저장하기 위한 공간

count : 목표한 모든 수를 찾기 위해 실행된 2번, 3번 행동의 수

tempCount : 하나의 목표한 수를 찾기 위해 실행된 2번, 3번 행동의 수

 

해결 과정

(1) Deque의 크기를 입력받고 1~10의 수로 초기화한다.

(2) 찾고자 하는 수의 개수만큼 아래 과정(3-6번 과정)을 반복한다.

(3) 만약 가장 앞의 값이 찾고자 하는 수이면 배열에서 뺀다.

(4) 다음 목표한 값을 찾을 때 까지 한 방향으로 돌리면서 움직인 횟수를 카운트(tempCount)한다.

(5) tempCount가 배열 크기의 절반 값 보다 크면 배열 크기에서 카운트 된 수를 빼서 다시 카운트 수에다가 넣는다.

(6) tempCount를 count에 추가하고 다음 목표 수를 찾는다.

(7) count를 출력한다.

 

3. 최종코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Deque<Integer> deque = new ArrayDeque<>();

        for(int i=1; i<=n; i++){
            deque.addLast(i);
        }

        int count = 0;


        StringTokenizer commandToken = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++){
            int value = Integer.parseInt(commandToken.nextToken());

            int tempCount = 0;
            while(deque.getFirst()!=value){
                deque.addLast(deque.pollFirst());
                tempCount++;
            }

            if(tempCount>deque.size()/2){
                tempCount = deque.size()-tempCount;
            }

            count = count+tempCount;

            deque.pollFirst();
        }

        bw.write(Integer.toString(count));

        br.close();
        bw.close();
    }
}