[백준] 회전하는 큐 1021번 - Java

GOSHK·2022년 2월 7일
0

[백준] Java

목록 보기
17/49
post-thumbnail

[백준] 회전하는 큐 1021번

나의 풀이

public class RotatingQueue {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        int M = Integer.parseInt(s[1]);
        int count = 0;

        LinkedList<Integer> deque = new LinkedList<>();
        for(int i = 1; i < N + 1; i++) {
            deque.add(i);
        }

        String[] nums = br.readLine().split(" ");
        for(int i = 0; i < M; i++) {
            int index = 0;
            int halfIndex = 0;
            int pickNum = Integer.parseInt(nums[i]);
            if(deque.peekFirst() == pickNum) {
                deque.pollFirst();
                continue;
            }

            index = deque.indexOf(pickNum);

            if(deque.size() % 2 == 0) {
                halfIndex = deque.size() / 2 - 1;
            } else {
                halfIndex = deque.size() / 2;
            }

            if(index > halfIndex) {
                while(deque.peekFirst() != pickNum) {
                    count++;
                    deque.addFirst(deque.pollLast());
                }
            } else {
                while(deque.peekFirst() != pickNum) {
                    count++;
                    deque.addLast(deque.pollFirst());
                }
            }
            deque.pollFirst();
        }
        System.out.println(count);
    }
}
  • Queue 를 사용할 경우 get 이나 indexOf 와 같이 큐 안에서 원소를 찾는 메소드가 없기 때문에 LinkedList 나 List 를 사용하는 것이 좋다.
  • 만약 뽑아야할 수가 큐의 첫번째 요소와 같다면 큐를 좌, 우로 움직일 필요가 없으므로 count를 증가시키지 않고 바로 빼주고 continue 를 통해 다음 연산을 진행한다.
  • 같지 않다면 움직여 줘야 한다.
  • 우선 뽑아야할 숫자가 현재 큐에서 몇번째 인덱스에 있는지 알아야 한다. 그렇기 때문에 indexOf 메소드를 사용해서 인덱스를 추출해준다.
  • 인덱스가 큐의 중간보다 크다면 오른쪽으로, 작다면 왼쪽으로, 같다면 좌우 상관없이 움직여 줘야 한다.
  • 하지만 큐가 짝수이거나 홀수일 때를 주의해야 한다. 컴퓨터는 인덱스를 0부터 세기 때문에 짝수일 경우는 큐의 사이즈를 2로 나눌 경우 중간 값을 넘어가기 때문이다. 따라서 큐의 사이즈가 짝수라면 2로 나눈 값에서 -1을 해주고, 홀수라면 그냥 2로 나눠준 값을 중간 인덱스 값으로 활용한다.
  • 만약 뽑아야할 숫자의 인덱스가(index) 중간 인덱스(halfIndex) 보다 크다면, 큐의 첫번째 원소가 뽑아야 할 숫자(pickNum)과 같아질 때까지 오른쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
  • 반대로 중간 인덱스보다 작거나 같으면 똑같이 pickNum과 같아질 때까지 왼쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
  • 이동이 모두 끝난 후에는 큐에서 해당 원소를 제거해준다.

0개의 댓글