백준 1021번 회전하는 큐 [Queue] :: 마이구미

이번 글은 백준 1021번 회전하는 큐를 다룰 것이다.

정답률 33%정도이지만 쉬운 문제이다.

1021번 회전하는 큐 - https://www.acmicpc.net/problem/1021

Github - https://github.com/hotehrud/acmicpc

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이 때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

문제는 정확하게 이해하는 것이 필수다!

본인과 같이 바보처럼 해석하고 풀면 왜 틀리냐고 한탄만 할 것이다.

문제의 3가지 연산의 핵심은 1번 연산이다.

큐와 같이 맨 앞에 있는 요소를 뽑는 것이다.

뽑고 싶은 요소가 입력으로 주어졌을 때 맨 앞에 당연히 없게 주어지는 경우가 있다.

(첫번째 요소를 head라고 하고, 맨 끝의 요소를 tail이라고 명시하겠다)

이 때 2번이나 3번 연산을 통해 head를 왼쪽이나 오른쪽으로 이동시켜 해당 요소가 head에 온다면 그때 1번 연산을 수행하는 것이다.

결국 head에 뽑을 요소가 없다면 올 때까지 2번 3번 연산을 수행하여 head에 오게 하면 된다.

또 하나! 중요한 것은 2번, 3번 연산의 최솟값을 구하는 문제임으로 2번, 3번 연산 중 어떤 걸 수행할 지 잘 고려해야한다는 것이다.

무작정 2번이나 3번 연산을 수행한다면 최솟값이 아닐 경우가 발생하기 때문이다.

어떻게 2번, 3번 연산 중 최솟값을 구하기 위해 고려할 것인가?

뭐 이건 뻔하다. 다들 알 것이라 생각한다.

사실 이 문제는 문제만 제대로 이해한다면 쉽게 풀 수 있으니까 혹시나 틀렸던 사람이라면 분명 문제를 잘못 이해했을 것이다. 

아무튼 뽑을 요소의 위치를 기준으로 head쪽에 가까운지 tail쪽에 가까운지 계산하면 된다.

예를 들자면 아래와 같다.

int pos = list.indexOf(num);
int size = list.size();
int left = pos;             // head와의 거리
int right = size - pos - 1; // tail과의 거리

head와의 거리는 뽑을 요소의 인덱스라고 친다면, tail과의 거리는 크기 - head와의 거리 - 1이 된다.

별 거 없다. 그렇다. 계속 말하지만 문제만 정확히 이해한다면 쉽게 풀리는 문제다.

그리고 ArrayList를 사용하는 경우가 많다.

간단하게 핵심만 말하겠다.

ArrayList의 경우는 데이터 추가 삭제 시 임시배열을 이용하여 복사하게 된다. 

즉, 밀어내기식을 통해 처리되기 때문에 성능이 저하될 수 있다.

반면 LinkedList의 경우는 위치정보를 통해 처리됨으로 데이터 추가 삭제 시 용이하다.

자세한 건 아래 링크를 통해 확인하자. 이해하기 쉽게 설명되어있다.

http://seeit.kr/36

궁금하면 다들 한번 풀어보자.

링크 걸어둘테니 이 문제를 풀면 쉽게 풀릴 것이고, ArrayList와 LinkedList의 차이를 볼 수 있다.

소스는 아래에 두겠다.

유사한 문제 - 백준 2164번 카드1

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

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		String[] nm = bf.readLine().split(" ");
		String[] seq = bf.readLine().split(" ");

		int N = Integer.parseInt(nm[0]);

		CircleQueue q = new CircleQueue(N, seq);
		
		System.out.println(q.getCount());
		
		bf.close();
	}
}

class CircleQueue {
	private LinkedList<Integer> list = new LinkedList<Integer>();
	private int count = 0;
	private String[] seq;

	CircleQueue(int size, String[] seq) {
		for (int i = 1; i <= size; i++) {
			list.add(i);
		}
		this.seq = seq;
		start();
	}

	private void start() {
		int length = seq.length;

		for (int i = 0; i < length; i++) {
			int n = Integer.parseInt(seq[i]);
			operate(n);
		}
	}

	private void operate(int num) {
		while (true) {
			int pos = list.indexOf(num);
			int size = list.size();
			int left = pos;
			int right = size - pos - 1;

			if (left == 0) {
				list.remove(pos);
				break;
			}

			if (left <= right) {
				//2번 연산 왼쪽으로 한칸 이동
				list.addLast(list.removeFirst());
				++count;
			} else {
				//3번 연산 오른쪽으로 한칸 이동 
				list.addFirst(list.removeLast());
				++count;
			}
		}
	}

	public int getCount() {
		return count;
	}
}