백준1021번) 회전하는 큐

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

1021번: 회전하는 큐

◇ 문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

◇ 입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

◇ 출력

첫째 줄에 문제의 정답을 출력한다.

---

◆ 풀이

왼쪽/오른쪽으로 이동 연산의 최소 호출 횟수는 어떻게 계산할 수 있을까?

찾으려는 숫자의 위치가 1에 가까운지, 혹은 현재 기준 큐의 스택의 사이즈의 값에 가까운지에 따라 다를 것이다.

 

여기서 중요한 점은 입력에서 주어지는 위치는 큐의 가장 최초 위치라는 점이다.

이 부분을 간과하면 문제가 있을 것이다.

 

그렇다면 어떻게 큐의 최초 위치를 기억하면서 할 수 있을까?

Queue가 아니라 Array를 사용하고, First와 Last를 표시하는 용도의 int를 사용하면 어떨까?

 

왼쪽으로 이동시킬 때마다 index를 1 감소 시키고, (만약 0 미만인 경우에는 최대값으로 지정되도록)

오른쪽으로 이동시킬 떄마다 index를 1 증가 시키면 최소한의 데이터와 행동으로도 가능할 것으로 보인다.

 

그리고 왼쪽/이동/데이터 poll 등의 처리를 할 때마다 입력 받은 int[] array의 위치값을 더하고 빼준다.

1번을 진행하면 왼쪽으로 이동시키는 연산을 호출해주는 것은 꼭 잊지 말고 처리해야할 것이다.

 

아이디어 구상은 이 정도로 마치고 바로 구현해보자!

import java.util.*;

public class Main {

    private static int _currentQueueSize;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 큐 사이즈 및 배열 사이즈 준비
        String[] firstLine = scanner.nextLine().split(" ");
        _currentQueueSize = Integer.parseInt(firstLine[0]);
        int pickCount = Integer.parseInt(firstLine[1]);

        // 찾아야 할 위치가 적힌 배열 준비
        List<Integer> pickArray = new LinkedList<Integer>();
        String[] secondLine = scanner.nextLine().split(" ");
        for(int i=0, iMax = secondLine.length; i<iMax; i++){
            pickArray.add(Integer.parseInt(secondLine[i]));
        }

        // 결과를 출력할 데이터
        int result = 0;

        while(pickArray.size()>0){
            // 뽑으려는 숫자 위치;
            int pickNumIndex = pickArray.get(0);
            int wayAndCount = findNearestWay(pickNumIndex);

            if(wayAndCount!=0){
                move(pickArray, wayAndCount);
                result+=Math.abs(wayAndCount);
            }

            pollFirst(pickArray);
        }

        System.out.println(result);
    }

    private static int findNearestWay(int pickIndex){
        int result = 0;
        int diff = _currentQueueSize - pickIndex + 1;
        if(diff >=pickIndex){
            result =-pickIndex + 1;
        }
        else{
            result = diff;
        }
        // 음수는 왼쪽, 양수는 오른쪽으로 이동
        return result;
    }

    private static void pollFirst(List<Integer> queue){
        // 가장 앞에 있는 데이터를 뺀다.
        queue.remove(0);
        // 사이즈를 줄인다.
        _currentQueueSize--;
        // 남은 모든 데이터의 위치 index값을 1씩 줄인다.
        move(queue, -1);
    }

    public  static void move(List<Integer> queue, int num){
        int currentValue = 0;
        for(int i=0, iMax = queue.size(); i<iMax; i++){
            currentValue = queue.get(i) + num;
            int changeNum = currentValue < 1 ? _currentQueueSize+currentValue  : currentValue>_currentQueueSize ? currentValue - _currentQueueSize : currentValue;
            queue.set(i, changeNum);
        }
    }
}

쓰다보니 코드가 많이 길어졌다;;

최초에 구상했던 Array는 사용을 포기하고 List로 노선을 바꾸었다.

메모리와 시간을 보니 제대로 푼 것 같지가 않은 기분이다...

풀고도 찝찝한 기분이 든다.

메모리를 너무 많이 잡아먹고, 시간도 굉장히 오래 걸렸다.

아마 좀 무식한 방법이었나보다... ㅎㅎ ㅠㅠ

다른 방법을 고민해봐야겠다.