[Baekjoon/Java] 회전하는 큐

문제

1021번: 회전하는 큐

풀이

N=10, M=3, 원소의 위치={2,9,5}라고 할 때 2번, 3번 연산에 따라 아래와 같이 진행되어야한다.

왼쪽으로 이동했을 때와 오른쪽으로 이동했을 때의 거리를 계산하여 가장 짧은 쪽의 방향을 선택하여 수행하면 되는 문제이다.

아래 코드는 직접 LinkedList로 구현하여 양방향 이동을 가능하게하였다.

import java.util.*;  
import java.util.stream.Collectors;  
import java.util.stream.IntStream;  

/**  
 * value -> next  
 */  
class Node {  
    Node next;  
    Integer value;  

    public Node(int value) {  
        this.value = value;  
    }  
}  

class CustomQueue {  
    private Node head;  
    private int size = 0;  


    public CustomQueue(Collection<Integer> collection) {  
        fromCollection(collection);  
        this.size = collection.size();  
    }  

    /**  
     * collection 객체를 받아 LinkedList 로 변환  
     */  
    private void fromCollection(Collection<Integer> collection) {  
        for (int num : collection) {  
            Node node = new Node(num);  
            if (head  null) {  
                head = node;  
            } else {  
                Node temp = head;  
                while (temp.next != null) {  
                    temp = temp.next;  
                }  
                temp.next = node;  
            }  
        }  
    }  

    public int size() {  
        return size;  
    }  

    /**  
    * 첫 번째 요소를 뽑고 전체 크기 - 1  
    */  
    public void firstElement() {  
        head = head.next;  
        size--;  
    }  

    /**  
    * head와 n과의 거리를 계산하여 반환  
    * @param n 찾아야하는 원소  
    */  
    public int leftDistance(int n) {  
        int d = 0;  
        Node temp = head;  
        while (temp != null) {  
            if (temp.value  n) {  
                break;  
            }  
            temp = temp.next;  
            d++;  
        }  
        return d;  
    }  

    /**  
    * n만큼 왼쪽으로 이동  
    */  
    public void leftMove(int n) {  
        for (int i=0; i<n; i++) {  
            Node leftNode = head;  
            head = head.next;  
            leftNode.next = null;  
            Node temp = head;  
            while (temp.next != null) {  
                temp = temp.next;  
            }  
            temp.next = leftNode;  
        }  
    }  

    /**  
    * n만큼 오른쪽으로 이동  
    */  
    public void rightMove(int n) {  
        for (int i=0; i<n; i++) {  
            Node temp = head;  
            while (temp.next.next != null) {  
                temp = temp.next;  
            }  
            Node rightNode = temp.next;  
            temp.next = null;  
            rightNode.next = head;  
            head = rightNode;  
        }  
    }  
}  

public class RotationQueue {  
    //O(NM)  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int N = scanner.nextInt();  
        int M = scanner.nextInt();  
        int[] targetNums = new int[M];  
        for (int i=0; i<M; i++) {  
            targetNums[i] = scanner.nextInt();  
        }  

        CustomQueue q = new CustomQueue(IntStream.rangeClosed(1, N).boxed().collect(Collectors.toList()));  
        int cnt = 0;  
        for (int targetNum : targetNums) {  
            int left = q.leftDistance(targetNum);  
            int right = q.size() - left;  
            if (left <= right) {  
                q.leftMove(left);  
                cnt += left;  
            } else {  
                q.rightMove(right);  
                cnt += right;  
            }  
            q.firstElement();  
        }  
        System.out.println(cnt);  
    }  
}

Queue를 활용하는 문제
시간복잡도: O(NM)