백준)Q.1021_회전하는 큐

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

1021번: 회전하는 큐

 

문제

지민이는 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

10 3

1 2 3

예제 출력 1

0

예제 입력 2

10 3

2 9 5

예제 출력 2

8

예제 입력 3

32 6

27 16 30 11 6 23

예제 출력 3

59

예제 입력 4

10 10

1 6 3 2 7 9 8 4 10 5

예제 출력 4

14

  import java.util.LinkedList;
  import java.util.Scanner;
   
  public class test {
   
         static int count = 0;
         static LinkedList dq = new LinkedList();
   
         static void Cal2() {
               dq.offer(dq.peekFirst());
               dq.pollFirst();
               count++;
         }
   
         static void Cal3() {
               dq.offerFirst(dq.peekLast());
               dq.pollLast();
               count++;
         }
   
         public static void main(String[] args) {
   
               Scanner sc = new Scanner(System.in);
   
               int size = sc.nextInt();
               int pick = sc.nextInt();
               int[] arr = new int[pick];
               int check = 0;
   
               for (int i = 1; i <= size; i++) {
                      dq.add(i);
               }
   
               for (int i = 0; i < pick; i++) {
                      arr[i] = sc.nextInt();
               }
   
               while (check < pick) {
                      int first = (int) dq.peekFirst();
   
                      while (arr[check] != first) {   
                             int tmp = arr[check];
                             int frontIndex = dq.indexOf(Integer.valueOf(tmp));
                             int backIndex = dq.size() - dq.indexOf(Integer.valueOf(tmp));
   
                             if (frontIndex <= backIndex) {
                                   Cal2();
                             } else if (frontIndex > backIndex) {
                                   Cal3();
                             }
                             first = (int) dq.peekFirst();
                      }
                      dq.pollFirst();
                      check++;
                      if (check > pick)
                             break;
               }
               System.out.println(count);   
         }   
  }
  
 

 

예제2번으로 풀이를 해보자면, 

첫째줄에 10과 3이 입력되면 1부터 10까지의 수에서 세개의 숫자를 뺀다는 조건이며 뺄 숫자는 다음 줄에 주어진다. 

2, 9, 5. 순서는 입력된 순서 그대로 제거되어야 한다.

알고리즘을 표로 나타내 보자.

처음에 암만 생각해도 8번이 안나오던데 무조건 뺄 수를 앞에두어야 한다는 사실을 자꾸 잊고 맨 마지막에 두고 계산을 하고 있었음;; 

 

어찌됐든 알고리즘은 저러하고 8을 출력하면 된다. 

 

일단 2번 연산과 3번 연산을 실행해줄 메소드를 만들었다. 

 

static void Cal2() {

dq.offer(dq.peekFirst());

dq.pollFirst();

count++;

}

덱의 앞에 있는 값을 덱의 맨 뒤로 이동하고(offer) 앞에 있는 값을 제거한 후, count를 올려주는 메소드.

 

static void Cal3() {

dq.offerFirst(dq.peekLast());

dq.pollLast();

count++;

}

덱의 맨 뒤에 있는 값을 덱의 맨 앞으로 이동하고(offerFirst) 맨 뒤에 있는 값을 제거한 후, count를 올려주는 메소드.

 

 

static int count = 0;                           // 최종 return할 연산 count변수

static LinkedList dq = new LinkedList();  // 덱. Index를 알기 위해서 Linkedlist를 이용했다.

 

 

int size = sc.nextInt();      // 처음 입력받을 수(범위. 1~size)  

int pick = sc.nextInt();     // 뺄 값의 갯수  

int[] arr = new int[pick];  // 뺄 값을 저장할 배열  

int check = 0;               // 배열에 입력된 값들이 모두 빠졌는지 확인할 변수(배열에 저장된 값을 뺄때마다 올려줌) 

 

 

for (int i = 1; i <= size; i++) {

dq.add(i);

} 

1부터 입력받은 size만큼 덱에 넣어줌.

 

 

for (int i = 0; i < pick; i++) {

arr[i] = sc.nextInt();

}

덱에서 뺄 값을 arr에 넣어줌. 

 

 

while (check < pick) {            // check(뺀 값)이 pick(뺄 값의 갯수)과 같기 전까지 반복할 while문 

int first = (int) dq.peekFirst();  // 덱의 맨 앞의 값을 저장할 first변수 

 

while (arr[check] != first) {      // arr에 들어있는 원소가 덱의 맨 앞의 값과 같을때 까지 반복할 while문 

int tmp = arr[check];             // 검사할 원소를 tmp에 저장 

int frontIndex = dq.indexOf(Integer.valueOf(tmp));    // 검사할 원소가 덱에서 몇번째에 있는지 index값을 저장할 변수

int backIndex = dq.size() - dq.indexOf(Integer.valueOf(tmp)); // 뒤에서 몇번째에 있는지 index값을 저장할 변수 

 

if (frontIndex <= backIndex) {         // frontIndex가 backIndex보다 작거나 같다면 2번 연산 실행. 

Cal2();

} else if (frontIndex > backIndex) {   // frontIndex가 backIndex보다 크다면 3번 연산 실행.

Cal3();

}

first = (int) dq.peekFirst(); // 덱의 맨 앞 값을 저장. 

}

 

dq.pollFirst();      // 덱의 맨 앞 값을 제거한다.(1번연산) 

check++;           // 제거가 되었으면 check를 올려주어 그 다음 수를 검사한다. 

if (check > pick)  // check(뺀 값)가 pick(뺄 값의 갯수)보다 커지면 반복문 탈출.

break;

}

System.out.println(count);