[BAEKJOON] 1021 회전하는 큐

문제 요약

• 알고리즘 분류: 큐, 데크
• 난이도: Silver4
• 문제내용:
  • 배열 담을수 있는 공간 N
  • 원소는 첫뻔째 원소만 뽑을 수 있다.
  • 앞에 원소를 뒤로 옮길수 있다.
  • 뒤에 원소를 앞으로 옮기수있다.
  • M개의 빼야될 목록을 주면 최소 몇번 이동해야는 구해라.

문제풀이

 이번 문제 큐와 데크에 관련된 문제이다. 일반적으로 배열이나 리스트로 구현하기에는 힘들어서 모듈을 들고 와서 처리를 해야한다. 큐와 데크에 대한 자세한 내용은 아래의 사이트에서 확인하면된다.

https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0) 

큐(자료구조) - 나무위키

 큐와 데크에 대한 개념을 알면 모듈을 활용해서 푸는것이다. 그래서 모듈에 대한 문서나 공부하면 쉽게 응용할수 있어서 어려운 문제가 아니다.

1. 데크랑  관련된 자료구조를 선언한다.
2. 찾을 데이터의 인덱스의 위치를 파악해서 앞, 뒤중 더 빨리 찾을 수 있는 것을 선택한다.
3. 0번째 인덱스가 원하는 데이터가 될때까지 앞에서 뒤 또는 뒤에서 앞을 데이터를 옮긴다. 그리고 하나 옮길때마다 데이터를 개수를 추가한다.
4. 찾았으면 0번째 인덱스를 pop한다.

Code

Python

 파이썬은 deque라는 모듈이 있다. deque는 큐나 덱에서 뿐만 아니라 코테에 자주나오는 BFS 알고리즘에도 자주사용되니 무조건 알아둬야 하는 라이브러리 모듈이다.

from collections import deque
queue = deque()
N, M = map(int, input().split())
queue = deque(list(range(1, N + 1)))

count = 0
for num in list(map(int, input().split())):
    flag = queue.index(num) >= len(queue) / 2
    while num != queue[0]:
        if flag:
            queue.extendleft([queue.pop()])
        else:
            queue.append(queue.popleft())
        count += 1
    queue.popleft()
    
print(count)

Java

 자바같은 배열이 있는 언어는 파이썬과 다르게 앞뒤 데이터가 추가가 안된다. 배열로는 구현 할 수 있지만 실버문제 치고는 구현하기에는 시간도 걸릴뿐만 아니라 코드 길이도 길어져서 최대한 간단하게 구현 하는것이 좋다. 라이브러리 모듈중 LinkedList가 있는데 LinkedList는 배열처럼 인덱스로 이루진것이 아니라 객체 단위로 연결이 되어있어서 삽입 삭제가 용이하다. LinkedList도 전공자든 비전공자이든 알아두어야 되는 구조이니 공부는 무조건 해두자!!!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

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 M = Integer.parseInt(st.nextToken());
		LinkedList<Integer> queue = new LinkedList<Integer>();
		for(int i = 0; i < N; i++) {
			queue.offer(i + 1);
		}
		st = new StringTokenizer(br.readLine());
		int count = 0;
		int num;
		boolean flag;
		while(M-- > 0) {
			num = Integer.parseInt(st.nextToken());
			flag = queue.indexOf(num) > queue.size() / 2;
			while(queue.getFirst() != num) {
				if(flag) {
					queue.offerFirst(queue.pollLast());					
				}else {
					queue.offerLast(queue.pollFirst());
				}
				count++;
			}
			queue.pollFirst();
		}
		System.out.println(count);
	}
	
}