자료구조 5/9 - 큐

손으로 그려보는 자료구조

연관문제 풀이

회전하는 큐 - 백준 1021번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Qu {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;

        String[] s = (br.readLine()).split(" "); // deque size, 뽑을 item 개수
        int size = Integer.parseInt(s[0]);
        String[] targets = (br.readLine()).split(" ");

        Integer[] qu = new Integer[size];
        for (int i = 0; i < size; i++) {
            qu[i] = i + 1;
        }
        List<Integer> queue = new ArrayList<>(Arrays.asList(qu));

        // 배열을 좌우로 탐색해서 해당 타깃 찾아 내기 - 몇칸 이동했는지 찾고 그걸 size에서 뺀 숫자중 작은 숫자 채택
        // size 1 감소시키기
        // 위와 같은 행위를 모든 타깃을 찾을때까지 한 뒤 answer 에 더해서 출력하기

        int cur = 0;
        int step = 0;
        for (String target : targets) {
            int t = Integer.parseInt(target);
            

            while (queue.get(cur) != t) {
                cur++;
                step++;
                if (cur == size) {
                    cur = 0;
                }
            }
            queue.remove(cur);

            if (step >= size - step) {
                answer += size - step;
            } else {
                answer += step;
            }

            step = 0;
            size--;

            if (size == cur) {
                cur = 0;
            }
        }

        System.out.println(answer);
    }
}