Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

19. 큐, 덱

큐와 덱을 구현하고 사용해 봅시다.

Java / Python

6. 회전하는 큐

1021번

덱을 활용하여 큐를 회전시키는 문제

이번 문제는 N개의 원소를 포함하고 있는 양방향 순환 큐를 이용하는 문제입니다. 자세히 보면, 이 큐에서 3가지 연산을 수행할 수 있고 뽑으려고 하는 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하는 문제입니다. 즉, 뽑으려 하는 원소가 덱의 중앙에서 끝쪽에 가까운 쪽 방향으로 이동시켜 뽑는 원소가 첫 번째 위치에 갈 때까지 반복
한 다음, 원소를 뽑는 방식입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
        
		LinkedList<Integer> deque = new LinkedList<Integer>();		
        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int cnt = 0;	// 2, 3번 연산 횟수 누적 합
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());	// 큐의 크기 N
		int M = Integer.parseInt(st.nextToken());	// 뽑는 숫자 개수
		
		for(int i = 1; i <= N; i++) {
			deque.offer(i);
		}
		
		int[] seq = new int[M];	// 뽑는 수 index를 담은 배열
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < M; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < M; i++) {
						
			// 덱에서 뽑으려는 숫자의 index
			int target_idx = deque.indexOf(seq[i]);
			int half_idx;

			if(deque.size() % 2 == 0) {
				half_idx = deque.size() / 2 - 1;
			}
			else {
				half_idx = deque.size() / 2;
			}
						
			if(target_idx <= half_idx) { // 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
				// index 보다 앞에 있는 원소들 모두 뒤로 (2번 연산)
				for(int j = 0; j < target_idx; j++) {
					int temp = deque.pollFirst();
					deque.offerLast(temp);
					cnt++;
				}
			}else {	// 중간 지점보다 원소의 위치가 뒤에 있는 경우 
				// index를 포함한 뒤에 있는 원소들 모두 앞으로 (3번 연산)
				for(int j = 0; j < deque.size() - target_idx; j++) {
					int temp = deque.pollLast();
					deque.offerFirst(temp);
					cnt++;
				}
			
			}
			deque.pollFirst();	// 연산 끝 -> 맨 앞 원소 삭제
		}
		
		System.out.println(cnt);
		
	}
}

• Python

import sys
n, m = map(int, sys.stdin.readline().split())
seq = list(map(int ,sys.stdin.readline().split()))
deque = [i for i in range(1, n + 1)]
cnt = 0
for i in range(m):
    q_len = len(deque)
    q_idx = deque.index(seq[i])
    if q_idx < q_len - q_idx:
        while True:
            if deque[0] == seq[i]:
                del deque[0]
                break
            else:
                deque.append(deque[0])
                del deque[0]
                cnt += 1
    else:
        while True:
            if deque[0] == seq[i]:
                del deque[0]
                break
            else:
                deque.insert(0, deque[-1])
                del deque[-1]
                cnt += 1
print(cnt)