1021 - 회전하는 큐

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

1021번: 회전하는 큐

 

문제요약

• 1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
• 2. 왼쪽으로 한 칸 이동. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
• 3. 오른쪽으로 한 칸 이동.  이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
• 2번 3번의 연산을 최소로하면서 내가 원하는 숫자를 뽑아내는 데, 필요한 2번 3번 연산의 횟수를 구하는 문제

문제를 보는 순간,

나열된 숫자가 홀수개인지 짝수개인지가 중요한 문제라고 생각이 들었다.

홀수 개일 경우,
1 2 3 4 5 에서,
3을 중앙값인 3을 기준으로 3보다 작거나 같으면 왼쪽 (2번 연산)
                                            3보다 크다면 오른쪽(3번 연산)

짝수 개일 경우,
1 2 3 4 5 6 에서,
중간값으로 여겨지는 3 4를 보면,
4보다 작은 수는 왼쪽 (2번 연산)
4 보다 크다면 오른쪽(3번 연산)   (4은 어느쪽으로 움직여도 상관없음)

규칙을 얻었다.

양쪽으로 숫자를 옮겨주는 작업을 해야하고, 인덱스번호를 알아야하므로 LinkedList를 사용했다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token1 = new StringTokenizer(reader.readLine());
        LinkedList<Integer> dq = new LinkedList<>();

        int numLength = Integer.parseInt(token1.nextToken());
        int pickCnt = Integer.parseInt(token1.nextToken());
        StringTokenizer token2 = new StringTokenizer(reader.readLine());

        for (int i = 1; i <= numLength; i++) {
            dq.add(i);
        }

        int cnt = 0;
        int midIndex;
        for (int i = 0; i < pickCnt; i++) {
            int num = Integer.parseInt(token2.nextToken());
            int numIndex = dq.indexOf(num);

            if (dq.size() % 2 == 0) {
                midIndex = (dq.size() / 2) - 1;


            }else{
                midIndex = dq.size() / 2;
            }
            //왼쪽
            if(midIndex >= numIndex){
                for (int j = 0; j < numIndex; j++) {
                    dq.offerLast(dq.pollFirst());
                    cnt++;
                }
            }
            //오른쪽
            else{
                for (int j = dq.size(); j > numIndex; j--) {
                    dq.offerFirst(dq.pollLast());
                    cnt++;
                }
            }
            dq.pollFirst();

        }

        System.out.println(cnt);

    }

}

---

느낀점

문제를 보면서,

문제의 요구사항을 분석하고,

문제를 해결하기 위한 분기점을 찾고,

적절한 자료구조를 사용할 것인지를 체크하는 작업을 하는 방식을

제대로 익힌 것 같다. 이 후 문제들은 전부 지금과 같은 방향으로 접근하며

실력을 키워보자!