[Python][Java] 백준 1021번. 회전하는 큐

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

1021번: 회전하는 큐

문제 설명:

N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다.

첫번째 원소를 뽑았을 때 찾는 숫자가 맞으면 pop을 하고

첫번째 원소와 뽑을 숫자가 맞지 않다면 왼쪽으로 이동시키거나 오른쪽으로 이동시킬 수 있다.

이때 원소들을 찾을 때까지 몇 번의 이동이 있었는지 확인하는 문제이다.

 

풀이 설계:

• 양방향 큐이기 때문에 deque로 이 문제를 푼다.
• dq의 첫번째 원소의 값과 찾는 숫자의 인덱스를 비교한다. 같으면 반복문을 끝내고 다음 원소를 찾는다.
• dq의 첫번째 원소와 찾을 숫자가 같지 않다면
  • dq의 길이/2 와 dq의 인덱스의 길이를 비교하여
    • 찾을 원소의 위치보다 dq 길이/2가 더 크다면 앞의 원소를 빼서 뒤로 보내준다.
      • 찾을 원소가 dq길이의 반보다 앞에 있다는 의미이다.
  • dq에서 찾을 원소의 위치 > dq의 길이는 찾을 원소가 뒤쪽에 위치했다는 의미
    • 뒤에 있는 원소를 dq의 앞에 넣어준다. 

Python

import sys
#양방향 큐이기 때문에 deque로 이 문제를 푼다.
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
idxs= list(map(int, input().split()))

#dq에 1~10까지 넣어준다.
dq = deque([i for i in range(1, n+1)])
cnt = 0

for idx in idxs:
	# dq의 첫번째 원소의 값과 찾는 숫자의 인덱스를 비교한다. 
    while True:
    	# 같으면 반복문을 끝내고 다음 원소를 찾는다.
        if idx == dq[0]:
            dq.popleft()
            break
		# 찾을 원소의 위치보다 dq 길이/2가 더 크다면 앞의 원소를 빼서 뒤로 보내준다.
        elif dq.index(idx) < len(dq)/2:
            while dq[0] != idx:
            	# 찾을 원소가 dq길이의 반보다 앞에 있다는 의미이다.
                dq.append(dq.popleft())
                cnt += 1
        else:
            while dq[0] != idx:
            	# dq에서 찾을 원소의 위치 > dq의 길이는 찾을 원소가 뒤쪽에 위치했다는 의미
				# 뒤에 있는 원소를 dq의 앞에 넣어준다. 
                dq.appendleft(dq.pop())
                cnt += 1

print(cnt)

 

Java

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

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

        LinkedList<Integer> dq = new LinkedList<>();

        int n = in.nextInt();
        int m = in.nextInt();
        int[] idxs = new int[m];
        int cnt = 0;
        
        for (int i = 0; i < m; i++) {
            idxs[i] = in.nextInt();
        }

        for (int i = 1; i < n+1; i++) {
            dq.add(i);
        }
        for(int idx : idxs){
            while(true){
                if(idx==dq.getFirst()){
                    dq.removeFirst();
                    break;
                }

                else if(dq.indexOf(idx) > dq.size()/2){
                    while(dq.getFirst() != idx){
                        dq.addFirst(dq.removeLast());
                        cnt++;
                    }
                }else{
                    while(dq.getFirst() != idx){
                        dq.addLast(dq.removeFirst());
                        cnt++;
                    }
                }
            }
        }

        System.out.println(cnt);
    }
}