[JAVA]백준 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보다 작거나 같은 자연수이다.

 

# 출력

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

 

 

# 제출한 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.stream.Stream;

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());
        
        // 큐의 크기를 n에 담는다.
        int n = Integer.parseInt(st.nextToken());
        // 뽑아내려는 수의 개수를 m에 담는다.
        int m = Integer.parseInt(st.nextToken());
		
        // stream을 사용해서 뽑아내려는 수의 위치가 담긴 것을 int 배열에 담습니다.
        int[] numArr = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        // deque 구현체로 LinkedList를 사용합니다.
        LinkedList<Integer> deque = new LinkedList<>();
        
        // deque에 1 ~ n까지의 값을 집어넣습니다.
        for (int i = 1 ; i < n + 1; i++) {
            deque.add(i);
        }
        
        // 연산의 최솟값을 저장하는 count 변수 초기화
        int count = 0;
        
        // numArr 배열에 있는 숫자들을 각각 deque에서 찾기위해 반복문 실행
        for (int num : numArr) {
        
        	// num을 찾을때까지 while 반복문을 돌립니다.
            while (true) {
            	// deque에 첫번째 값을 firstNum 변수에 저장합니다.
                int firstNum = deque.getFirst();
                
                // firstNum과 num의 값이 같으면 첫번째 값을 deque에서 빼내고 while문을 종료합니다.
                if (firstNum == num) {
                    deque.removeFirst();
                    break;
                }
                
                // 찾을려는 num이 deque의 몇번째 인덱스에 있는 찾습니다.
                int numIndex = deque.indexOf(num);
                // deque안의 숫자들의 수에 나누기 2를 해서 deque의 절반 길이를 저장합니다.
                int dequeHalfSize = deque.size() / 2;
                
                // deque의 절반 길이를 사용해서 deque의 첫번째부터 num 값을 찾을지,
                // 아니면 마지막부터 값을 찾을지 확인합니다.
                // - deque의 중간 길이보다 numIndex가 작으면 앞에서 부터 num 값을 찾기
                // - deque의 중간 길이보다 numIndedex가 크면 뒤에서부터 num 값을 찾기
                if (numIndex <= dequeHalfSize) {
                    deque.addLast(deque.removeFirst());
                    count++;
                } else {
                    deque.addFirst(deque.removeLast());
                    count++;
                }

            }
        }

        System.out.println(count);
    }
}

 

 

 

풀면서 느낀점

• 문제 자체를 이해하는데 시간이 꽤 걸렸습니다.
• 블로그에 정리되어있는 내용을 보고서야 이해를 하고 문제를 풀었습니다.
• 다행이 다른사람이 구현한 코드를 전부 다 보고서 풀지는 않았습니다.
  => while문 안에 있는 세부 구현 부분은 안보고 풀었습니다.

 

 

# 참고자료

• 블로그 Stranger's LAB => 링크