Baekjoon1021: 회전하는 큐, 덱의 배열화

문제

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

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

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

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

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이1

덱에 있는 1 2 3 4 5에서 2를 꺼낸다고 하자. 왼쪽연산으로 1 오른쪽 연산으로 3이며

꺼내기 직전의 모습은

왼쪽연산 : 2 3 4 5 1

오른쪽 연산: 3 4 5 1 2 

여기서 2를 꺼내면? 모양이 같아진다

즉 빼고나서 오른쪽 연산이든 왼쪽연산이든 결과값은 같아지므로 단지 최소경로만 구해주면 된다.

덱의 자료 수의 절반 보다 작은 것이 바로 최소값이 된다.

그래서 아무렇게나 꺼내준뒤 덱 크기의 절반보다 크면 전체 size에서 빼주어 sum에 더하고

작으면 그대로 sum에 더해 최소경로를 구할 수 있다

덱 사용

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
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()," ");
	Deque<Integer> deque = new ArrayDeque<>();
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int[] extract = new int[M];
	for(int i=0; i<N; i++) {
		deque.offerLast(i+1);
	} //덱에 1부터 N의 값을 넣어줌
	
	st = new StringTokenizer(br.readLine()," ");
	
	for(int i=0; i<M;i++) { 
		extract[i]= Integer.parseInt(st.nextToken());
	} //배열 안에 값을 넣는다
	
	int sum=0;
	for(int i=0; i<M; i++) {
		int find = extract[i];
		int trying=0;  // 시행횟수 = pop을 카운트해준다
		int size = deque.size();
	    while(true) {
	    	if(deque.peekFirst()==find) {
	    		deque.pollFirst(); //찾는값과 일치하는 순간 값을 꺼내고 종료
	    		break;
	    	}
	    	trying++;
	    	deque.offerLast(deque.pollFirst());
	    }
	    sum+=trying>size/2?size-trying:trying;
	    // 부등호가 >=이 아님을 주의한다. 정수 연산이기 때문에 홀수를 나누는 경우를 주의한다
	    // 시행횟수가 자료크기의 절반 보다 크면 빼주고, 작으면 그대로 사용한다
     }
	 System.out.println(sum);
}
}

 

Scanner

import java.util.*;
public class Main {
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	Deque<Integer> deque = new ArrayDeque<>();
	int N=sc.nextInt(); int M=sc.nextInt();
	for(int i=N; i>0; i--)deque.push(i); //push를 통해 거꾸로 값을 넣어주며, i=N부터 시작
	int sum=0;
	while(M-->0){
		int find = sc.nextInt();
		int T=0; //trying을 T로 바꾸었다
		int size = deque.size();
	    while(true) {
	    	if(deque.peek()==find) {
	    		deque.pop(); //pollFirst와 같다
	    		break;}
	    	T++;
	    	deque.offerLast(deque.pop());} //뒤로 보내준다
	    sum+=T>size/2?size-T:T;}
	 System.out.print(sum);
}}

 

풀이2

덱에는 검색해서 삭제하는 메소드와 해당 값이 존재하는지 알아보는 메소드가 존재한다.

하지만 해당 요소의 값이 몇번째에 있는지 알려주는 메소드는 없다.

최소경로를 구하기 위해 덱에서 직접 시행을 통해 시행 횟수가 적은 것을 택하는 방식으로

최소경로를 구할 수 있지만 N이 50보다 작은 수이기에 배열을 사용함으로 단순화한다.

 

더 이상 입력이 없는 덱 → 배열

어떻게 구현할 수 있을까 생각해보았다

배열 안에서 원소들을 직접 다 옮길 필요가 없었다.

예를 들면 덱에 1 2 3 4 5 6 자료들이 있다면 오른쪽 연산을 했을 때 6 1 2 3 4 5가 된다

배열에서는 직접 옮기지 않고 [ 1, 2, 3, 4, 5, 6 ]에서 포커싱을 [ 1, 2, 3, 4, 5, 6 ] 으로 옮겨주면 된다

 

예제 2번을 배열을 통해 설명하면,

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 2 → 9 → 5

1) 입구 1을 기준으로 2와의 거리를 구한다: 오른쪽으로는 1, 왼쪽으로는 10-1 =9

2) 왼쪽 연산을 1번 진행한다: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3) 2번을 추출한다. 값은 0이되고 포커싱은 3에 간다. [1, 0, 3, 4, 5, 6, 7, 8, 9, 10]

4) 입구 3을 기준으로 9와의 거리를 구한다. 왼쪽으로 1+2 오른쪽으로 6이다

5) 왼쪽 연산을 3번 진행한다 [1, 0, 3, 4, 5, 6, 7, 8, 9, 10] 

6) 9를 추출하고 포커싱을 10으로 옮긴다 [1, 0, 3, 4, 5, 6, 7, 8, 0, 10]

7) 입구 10과 5와의 거리를 구한다. 왼쪽으로 4, 오른쪽으로 1+3

8) 왼쪽연산을 4번 진행한다 [1, 0, 3, 4, 5, 6, 7, 8, 0,10]

9) 5를 추출하고 모든 경로의 합을 구한다. sum = 1+3+4 =8

 

1) N크기의 배열과 뽑아야할 숫자의 개수M 크기의 배열을 만든다

2) N배열에는 1~N까지 순서대로 넣어주고 M배열에는 입력값들을 넣어준다

3) 반복문은 M번 작동한다

4) 현재 포커스 변수를 만들고 최소경로를 뽑아주는 메소드를 만든다

5) 메소드를 0을 만나면 카운트하지 않고 넘어간다. 포커스도 맞춰준다

 

배열 사용

import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	StringTokenizer st = new StringTokenizer(br.readLine()," ");
	int N = Integer.parseInt(st.nextToken());
	int M = Integer.parseInt(st.nextToken());
	int[] deque = new int[N];
	
	for(int i=0; i<N; i++) {
		deque[i]=i+1;
	} //덱 유사배열에 1부터 N의 값을 넣어줌
	
	int[] extract = new int[M];
	st = new StringTokenizer(br.readLine()," ");
	
	for(int i=0; i<M;i++) { 
		extract[i]= Integer.parseInt(st.nextToken());
	} //M안에 값을 넣는다
	
	int focus=0;
	int sum=0;
	
	for(int i=0; i<M; i++) {
		int find = extract[i];
		int index =0;
		for(int k=0; k<N; k++) {
			if(deque[k]==find) {
				index=k;
				k+=N;
			}
		}
		sum+=findMin(focus,find,deque,N);
     	while(i!=N-1) {
     		if(index==N-1)index=-1;
     		if(deque[index+1]!=0) {
     			focus = index+1;
     			break;
     		}
     		index++;
     	}
		}
	 System.out.println(sum);
}
public static int findMin(int focus, int find,int[] deque,int N) {
	int min1 = 0;
	int min2 = 0;
	int min=0;
	int start = focus;
	while(true) { //배열왼쪽이동 = 문제: 오른쪽 연산
		if(deque[start]==find) {
			break;
		}
		start--;
		if(start==-1) {
			start=N-1;
		}
		if(deque[start]!=0) {
			min1++;
		}
	}
	start = focus; //start 초기화
	while(true) { //배열오른쪽이동 = 문제: 왼쪽 연산
		if(deque[start]==find) {
			break;
		}
		start++;
		if(start==N) {
			start=0;
		}
		if(deque[start]!=0) {
			min2++;
		}
	}
	deque[start]=0;
	if(min1>=min2) {
		min=min2;
	}else {
		min=min1;
	}
	return min;
}
}

*매우 길지만 코드를 개선할 수 있을 것 같다