[BOJ][Java] 백준 1021번: 회전하는 큐

문제 설명

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

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

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

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

 

문제 풀이

이 문제를 해결하기 위해선

1. 우선 원하는 숫자가 어디에 있는지를 찾고

2. 해당 위차가 deque의 사이즈/2보다 작거나 같으면 왼쪽으로 아니면 오른쪽

으로 회전시켜주면 되는 문제입니다.

 

하지만 deque를 회전시키지 않고 해결할 수 있을까? 라는 고민을 하고 list에 1~n까지 담은 후에

뽑아야 하는 위치와 이전에 뽑힌 위치를 기준으로 거리를 비교하여 더하는 식으로 구현하였더니

이 방법 역시 가능하였습니다.

 

풀이 코드

<deque를 회전시켜 해결하는 방법>

package BOJ.p1000;

import java.util.*;

public class BOJ1021_deque {
    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        int[] store = new int[M];
        for(int i=0; i<M; i++)
            store[i] = sc.nextInt();

        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=1; i<=N; i++)
            dq.add(i);

        int count = 0;
        for(int i=0; i<M; i++) {
            Iterator<Integer> it = dq.iterator();
            int index = 0;
            while(it.hasNext()){
                if(it.next() == store[i])
                    break;
                index +=1;
            }
            if(index <= dq.size()/2) {
                while(index != 0) {
                    dq.addLast(dq.pollFirst());
                    index -= 1;
                    count+=1;
                }
            }
            else {
                while(index != dq.size()) {
                    dq.addFirst(dq.pollLast());
                    index+=1;
                    count+=1;
                }
            }
            dq.pollFirst();
        }
        System.out.println(count);
    }
}

 

<deque 회전 없이 해결하는 방법>

package BOJ.p1000;

import java.io.*;
import java.util.*;

public class BOJ1021_no_rotate {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int ans = 0, start = 0;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
        List<Integer> nList = new ArrayList<>();
        int[] mArr = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) mArr[i] = Integer.parseInt(st.nextToken());
        for(int i=1; i<=N; i++) nList.add(i);

        for(int i=0; i<M; i++){
            int index = nList.indexOf(mArr[i]);

            compareDist(start, index, nList.size());

            nList.remove(Integer.valueOf(mArr[i]));
            start = nList.size()==0 ? 0 : index%nList.size();
        }
        System.out.println(ans);
    }

    private static void compareDist(int start, int index, int len){
        if(start <= index){
            ans += Math.min(index - start, len - index + start);
        }else{
            ans += Math.min(start - index, len - start + index);
        }

        start = index;
    }
}

 

<출처>

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

1021번: 회전하는 큐