[백준] 1021번 : 회전하는 큐 - 자바[Java]

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

1021번: 회전하는 큐

 

나의 풀이 : ArrayList 사용

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        List<Integer> list = new ArrayList<>();
        int[] nums = new int[k];
        int cnt = 0;
        int i;

        st = new StringTokenizer(br.readLine());
        for (i = 0; i < k; i++)
            nums[i] = Integer.parseInt(st.nextToken());

        for (i = 1; i <= n; i++)
            list.add(i);

        for (i = 0; i < k; i++) {
            int idx = list.indexOf(nums[i]);

            if (idx <= list.size()/2) {
                for (int j = 0; j < idx; j++)
                    list.add(list.remove(0));
                cnt += idx;
            }
            else {
                for (int j = 0; j < list.size() - idx; j++)
                    list.add(0, list.remove(list.size()-1));
                cnt += list.size() - idx;
            }
            list.remove(0);
        }

        System.out.println(cnt);
    }
}

 

다른 풀이 : Deque를 구현하는 LinkedList 사용

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        LinkedList<Integer> list = new LinkedList<>();
        
        int cnt = 0;
        int i;
        
        for (i = 1; i <= n; i++)
            list.add(i);

        st = new StringTokenizer(br.readLine());
        for (i = 0; i < k; i++) {
            int num = Integer.parseInt(st.nextToken());
            
            int idx = list.indexOf(num);

            if (idx <= list.size()/2) {
                for (int j = 0; j < idx; j++)
                    list.offerLast(list.pollFirst());
                cnt += idx;
            }
            else {
                for (int j = 0; j < list.size() - idx; j++)
                    list.offerFirst(list.pollLast());
                cnt += list.size() - idx;
            }
            list.pollFirst();
        }

        System.out.println(cnt);
    }
}

 

 

참고: https://st-lab.tistory.com/216