[백준] 1021번 : 회전하는 큐 - JAVA [자바]

 
www.acmicpc.net/problem/1021

1021번: 회전하는 큐

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

 

이 문제는 덱(Deque)에 대한 이해만 있다면 크게 어렵지 않다.

 

혹여 덱(Deque)에 대해 자세하게 알고싶다면 다음 글을 참고하면 도움이 될 것이다.

 

st-lab.tistory.com/185

자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기

 

st-lab.tistory.com/187

자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기

 

 

 

 

 

그러면 문제를 한 번 보자.

 

문제에서는 세 가지 연산이 주어졌다.

 

 

 

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a₁, ..., a_k이었던 것이 a₂, ..., a_k와 같이 된다.

 

이 부분은 다음과 같다고 보면 된다.

 

 

 

 

2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a₁, ..., a_k가 a₂, ..., a_k, a₁이 된다.

 

 

 

 

 

3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a₁, ..., a_k가 a_k, a₁, ..., a_k-1이 된다.

 

 

 

 

 

 

 

 

 

이렇게 세 가지 연산이 주어지고 문제에서 중요한 것은 '2번 연산과 3번 연산이 최소가 되도록' 해야 한다는 점이다.

 

 

 

 

그리고 두 번째 라인에는 뽑고자 하는 숫자를 입력받는다.

그리고 두 번쨰 라인에서 숫자를 뽑을 때 2번 또는 3번 연산을 최소한으로 이용하여 뽑아야 한다는 것이 포인트다.

 

 

 

즉, 위의 예시로 보자면 아래와 같다.

 

[예시 1]

 

Deque = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

뽑을 숫자 : 1, 2, 3

 

-> 1번 연산을 3번 하면 됨. 즉, 2번 연산과 3번 연산은 사용 안하기 떄문에 0 출력

 

 

[예시 2]

 

Deque = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

뽑을 숫자 : 2, 9, 5

count : 2번과 3번연산 누적 횟수 

 

과정 1-1 : 2는 현재 덱에서 중앙 보다 앞에 존재하기 때문에 2를 뽑기 위해 2번 연산(앞에 있는 수를 뒤로 보냄)을 한 번 실행

<Result> 

Deque = {2, 3, 4, 5, 6, 7, 8, 9, 10, 1}

count = 1

 

과정 1-2 : 2를 뽑음.

<Result> 

Deque = {3, 4, 5, 6, 7, 8, 9, 10, 1}

count = 1

 

 

과정 2-1 : 9는 현재 덱에서 중앙 보다 뒤에 있기 때문에 9를 뽑기 위해 3번 연산(뒤에 있는 수를 앞으로 보냄)을 세 번 실행

<Result> 

Deque = {9, 10, 1, 3, 4, 5, 6, 7, 8}

count = 4

 

과정 1-2 : 9를 뽑음.

<Result> 

Deque = {10, 1, 3, 4, 5, 6, 7, 8}

count = 4

 

 

 

과정 3-1 : 5는 현재 덱에서 뒤에 있기 때문에 5를 뽑기 위해 3번 연산(뒤에 있는 수를 앞으로 보냄)을 네 번 실행

(물론 2번연산을 네 번 실행해도 된다. 다만 가독성을 위해 3번 연산을 하기로 한다.)

<Result> 

Deque =  {5, 6, 7, 8, 10, 1, 3, 4}

count = 8

 

과정 1-2 : 5를 뽑음.

<Result> 

Deque = {6, 7, 8, 10, 1, 3, 4}

count = 8

 

결과 : 8

 

 

 

이런 식이다.

 

 

즉, 전체 과정으로 보자면 두 가지 프로세스를 거친다.

 

1. 뽑고자 하는 원소가 덱의 중앙에서 끝쪽에 가까운 쪽 방향으로 이동(연산)하여 뽑고자 하는 원소가 첫 번째 위치에 갈 때까지 반복

2. 원소를 뽑음

 

 

 

이 두가지 프로세스를 구현해주면 된다.

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 두 가지 입력 방법을 통해 성능을 비교해보려한다.

참고로 Deque 자료구조는 LinkedList를 활용하여 구현하도록 하겠다. (찾고자 하는 원소의 위치를 쉽게 얻기 위함)

 

자세한 내용은 코드를 보면서 이해할 수 있도록 주석으로 상세하게 달아놓겠다.

 

 

1. Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

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

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		LinkedList<Integer> deque = new LinkedList<Integer>();
		
		int count = 0;	// 2, 3번 연산 횟수 누적 합 변수
		
		int N = in.nextInt();	// 큐의 크기(1 ~ N)
		int M = in.nextInt();	// 뽑으려는 숫자의 개수
		
		// 1부터 N까지 덱에 담아둔다.
		for(int i = 1; i <= N; i++) {
			deque.offer(i);
		}
		
		int[] seq = new int[M];	// 뽑고자 하는 수를 담은 배열
		
		for(int i = 0; i < M; i++) {
			seq[i] = in.nextInt();
		}
		
		
		for(int i = 0; i < M; i++) {			
			
			// 덱에서 뽑고자 하는 숫자의 위치(index) 찾기 
			int target_idx = deque.indexOf(seq[i]);
			int half_idx;
			/*
			 *  만약 현재 덱의 원소가 짝수 개라면 중간 지점을 
			 *  현재 덱의 절반 크기에서 -1 감소시킨다. 
			 *  
			 *  {1, 2, 3, 4} 일 때, 2를 중간지점으로 하면
			 *  인덱스는 1이기 때문
			 */
			if(deque.size() % 2 == 0) {
				half_idx = deque.size() / 2 - 1;
			}
			else {
				half_idx = deque.size() / 2;
			}
			
			
			// 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
			if(target_idx <= half_idx) {
				// idx 보다 앞에 있는 원소들을 모두 뒤로 보낸다. (2번 연산)
				for(int j = 0; j < target_idx; j++) {
					int temp = deque.pollFirst();
					deque.offerLast(temp);
					count++;
				}
			}
			else {	// 중간 지점보다 원소의 위치가 뒤에 있는 경우 
				// idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보낸다. (3번 연산)
				for(int j = 0; j < deque.size() - target_idx; j++) {
					int temp = deque.pollLast();
					deque.offerFirst(temp);
					count++;
				}
			
			}
			deque.pollFirst();	// 연산이 끝나면 맨 앞 원소를 삭제
		}
		
		System.out.println(count);
		
		
	}
}

 

 

 

 

생각한 것 보다 코드가 그리 길지도 않고 구현이 어렵지 않은 것을 볼 수 있다.

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M, 그리고 두 번째 줄의 수들을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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 {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		LinkedList<Integer> deque = new LinkedList<Integer>();
		
		int count = 0;	// 2, 3번 연산 횟수 누적 합 변수
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());	// 큐의 크기(1 ~ N)
		int M = Integer.parseInt(st.nextToken());	// 뽑으려는 숫자의 개수
		
		// 1부터 N까지 덱에 담아둔다.
		for(int i = 1; i <= N; i++) {
			deque.offer(i);
		}
		
		int[] seq = new int[M];	// 뽑고자 하는 수를 담은 배열
		
		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;
			/*
			 *  만약 현재 덱의 원소가 짝수 개라면 중간 지점을 
			 *  현재 덱의 절반 크기에서 -1 감소시킨다. 
			 *  
			 *  {1, 2, 3, 4} 일 때, 2를 중간지점으로 하면
			 *  인덱스는 1이기 때문
			 */
			if(deque.size() % 2 == 0) {
				half_idx = deque.size() / 2 - 1;
			}
			else {
				half_idx = deque.size() / 2;
			}
			
			
			// 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
			if(target_idx <= half_idx) {
				// idx 보다 앞에 있는 원소들을 모두 뒤로 보낸다. (2번 연산)
				for(int j = 0; j < target_idx; j++) {
					int temp = deque.pollFirst();
					deque.offerLast(temp);
					count++;
				}
			}
			else {	// 중간 지점보다 원소의 위치가 뒤에 있는 경우 
				// idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보낸다. (3번 연산)
				for(int j = 0; j < deque.size() - target_idx; j++) {
					int temp = deque.pollLast();
					deque.offerFirst(temp);
					count++;
				}
			
			}
			deque.pollFirst();	// 연산이 끝나면 맨 앞 원소를 삭제
		}
		
		System.out.println(count);
		
		
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 26804927  -  방법 2 : BufferedReader

채점 번호 : 26804925  -  방법 1 : Scanner

 

 

입력의 경우 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

---

• 정리

 

 

 

쓰고자 하는 자료구조를 적절히 선택해서 쓰면 되는 문제라 이 번 문제는 크게 어려운 점이 없었을 것이다. 정답률도 높은 것을 보니..

 

혹여나 이해가 안되거나 어려운 부분이 있다면 언제든 댓글 달아주시면 감사하겠다 :)