[BOJ][JAVA] 1021: 회전하는 큐

 

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

1021번: 회전하는 큐

---

오답노트(푸는 동안 사고과정 및 개선점)

오답은 아니고, 덱 자료구조를 처음 접하고 처음 풀어보는 문제였다. ArrayDeque이 있는 걸 알고 있어서 이거로 풀어보려고 했는데 중간값 탐색을 위해 indexOf가 있나 봤더니 없었다. 검색을 해보니 LinkedList로 인스턴스를만들어도 덱 처럼 쓸 수 있어서 해당 방법을 사용했다.

 

처음에 문제 이해가 안됐었다. N을 주고 몇번째를 뽑을 건지가 문제였는데, N까지의 수가 어떤 순서로 섞여있을 줄 알고 이렇게 뽑나 생각했다. 그러다 무슨 수를 뽑는게 아니라 몇번 째를 뽑는 것이므로 위치를 고려하는 문제였다. 따라서 그냥 1부터 N까지 쭉 채워주면 끝이다.

---

정답코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int pick = sc.nextInt();
        int cnt = 0;
        LinkedList<Integer> dq = new LinkedList<>();
        // ArrayDeque 을 사용한 deque은 indexOf가 없다.
        // Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            dq.offer(i);
        }
        for (int i = 0; i < pick; i++) {
            int t = sc.nextInt();
            // 타겟 위치 탐색
            int target = dq.indexOf(t);
            int m= dq.size() / 2;
            if (!dq.isEmpty() && t != dq.peekFirst()) {
                if (target <= m) { // 타겟이 왼쪽에 위치한 경우 -> 왼쪽으로 돌림
                    for (int j = 0; j < target; j++) {
                        dq.addLast(dq.pollFirst());
                        cnt++;
                    }
                    int tmp = dq.pollFirst();
//                    System.out.println(tmp);
                } else {
                    for (int j = 0; j < dq.size() - target; j++) {
                        dq.addFirst(dq.pollLast());
                        cnt++;
                    }
                    int tmp = dq.pollFirst();
//                    System.out.println(tmp);
                }
            } else {
                dq.pollFirst();
            }
        }
        System.out.println(cnt);
    }
}

 

 

주석 처리해둔 프린트문은 올바른 값이 위치해 있나 보려고 디버깅용으로 넣어둔 것이다. 

IDE가 없는 환경에서는 offer, poll, addLast, addFirst, pollLast, pollFirst, indexOf와 같은 메서드들이 있는 지 알 수 없으므로 반복해서 덱 문제를 풀어보는 수 밖에 없을 것 같다.

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^