[백준]1021. 회전하는 큐 (java, python)

📄 링크

회전하는 큐

---

💡 문제 분석

리스트의 양 끝에서 삽입, 삭제를 해야 하기 때문에 연결리스트를 사용했습니다

목표 숫자의 인덱스를 리스트에서 찾고, 처음과 끝 중 가까운 곳으로 시프트합니다

파이썬에서는 리스트를 합치는 것이 쉽기 때문에 반복문을 돌리지 않고 한꺼번에 처리할 수 있었습니다

---

⌨️ 코드

JAVA

import java.util.LinkedList;
import java.util.Scanner;

public class Q1021 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int ret = 0;

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

        while(M-- > 0) {
            int target = sc.nextInt();
            while(true) {
                if (list.getFirst() == target) {
                    list.pollFirst();
                    break;
                }

                if (list.indexOf(target) <= list.size() / 2)
                    list.addLast(list.pollFirst());
                else
                    list.addFirst(list.pollLast());

                ret++;
            }
        }
        System.out.println(ret);
    }
}

PYTHON

n, m = map(int, input().split())
arr = list(map(int, input().split()))
q = list(range(1, n + 1))
ret = 0
for target in arr:
    idx = q.index(target)
    if len(q) // 2 >= idx:
        ret += idx
    else:
        ret += len(q) - idx
    q = q[idx + 1:] + q[:idx]
print(ret)