[백준] 1021번 : 회전하는 큐

📚 문제

이미지를 클릭하시면 문제 링크로 연결됩니다.

---

📝 문제 이해

• N개의 원소를 포함하고 있는 양방향 순환 큐에서 원하는 숫자를 뽑기
• 인덱스는 한칸씩만 움직일 수 있다.

---

💡 문제 풀이

• 찾아야 하는 개수를 길이로 하는 인덱스 배열을 생성해서 찾아야 하는 숫자를 넣어준다.
  -> 큐의 인덱스
• 큐에 1부터 N까지 숫자를 넣는다.
• 큐의 맨 앞 원소가 찾아야 하는 숫자라면 제거 후 브레이크
• 아니라면 큐의 길이를 반으로 나눠 찾는 값이 더 작다면 앞의 값을 삭제해 맨 뒤로 보내고,
  정답 카운트를 증가시켜준다.
• 큐의 길이를 반으로 나눈 값이 찾는 값보다 더 크다면 뒤의 값을 삭제해 맨 앞으로 보내고, 정답 카운트를 증가시킨다.

---

💻 소스 코드

import java.io.*;
import java.util.*;

// 2일차 (큐) - 회전하는 큐
public class day02Baek1021 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));   // 번호 입력
        StringTokenizer st = new StringTokenizer(br.readLine());    // 첫 번째 줄 문자열 분리
        int n = Integer.parseInt(st.nextToken());   // 첫 번째 값은 큐의 크기
        int m = Integer.parseInt(st.nextToken());   // 두 번째 값은 찾아낼 숫자의 개수

        int[] idx = new int[m];
        st = new StringTokenizer(br.readLine());    // 두 번째 줄 문자열 분리
        for (int i = 0; i < m; i++) {
            idx[i] = Integer.parseInt(st.nextToken());  // 루프를 돌면서 배열에 찾아야 할 숫자의 위치 저장 (= 인덱스)
        }

        LinkedList<Integer> list = new LinkedList<>();  // 큐를 구현하고 있는 링크드리스트 클래스 객체 생성
        for (int i = 1; i <= n; i++) {
            list.offer(i);      // 링크드리스트에 숫자 저장
        }

        int cnt = 0;        // 정답을 출력할 카운트 변수 선언
        for(int i : idx){   // idx의 값을 i에 넣어서 루프를 돌린다.
            while (true) {
                if(list.peek() == i){   // list 의 맨 앞 원소가 i와 같다면 제거 후 브레이크
                    list.poll();
                    break;
                } else {
                    if (list.indexOf(i) < (double)list.size()/2){   // list 의 길이를 반으로 나눠 찾는 값이 더 작다면 위치가 list 의 앞쪽
                        while(list.peek() != i){    // i 가 list 의 맨 앞으로 올 때까지
                            list.offerLast(list.pollFirst());   // 맨 앞의 값을 삭제하고, 그 값을 맨 뒤로 보낸다.
                            cnt++;      // 정답 카운트 증가
                        }
                    } else {    // list 의 길이를 반으로 나눠 찾는 값이 더 크다면 위치가 list 의 뒷쪽
                        while(list.peek() != i){    // i 가 list 의 맨 뒤로 올 때까지
                            list.offerFirst(list.pollLast());   // 맨 뒤의 값을 삭제하고, 그 값을 맨 앞으로 보낸다.
                            cnt++;      // 정답 카운트 증가
                        }
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}