[알고리즘] 회전하는큐

package org.example.회전하는큐;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.*;

/**
 * packageName    : org.example.회전하는큐
 * fileName       : Main
 * author         : ipeac
 * date           : 2023-09-10
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2023-09-10        ipeac       최초 생성
 */
public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
            String input = br.readLine();
            String[] split = input.split(" ");
            int n = Integer.parseInt(split[0]);
            if (!(1 <= n && n <= 50)) {
                String errorMessage = MessageFormat.format("n 의 범위는 1 <= n <= 50 입니다. n = {0}", n);
                throw new IllegalArgumentException(errorMessage);
            }
            int m = Integer.parseInt(split[1]);
            if (!(1 <= m && m <= n)) {
                String errorMessage = MessageFormat.format("m 의 범위는 1 <= m <= {0} 입니다. m = {1}", n, m);
                throw new IllegalArgumentException(errorMessage);
            }
            
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            QueueRotator<Integer> queueRotator = new QueueRotator<>();
            for (int i = 1; i <= n; i++) {
                queueRotator.add(i);
            }
            
            List<Integer> targets = new ArrayList<>();
            
            while (st.hasMoreTokens()) {
                int target = Integer.parseInt(st.nextToken());
                if (!(1 <= target && target <= n)) {
                    String errorMessage = MessageFormat.format("target 의 범위는 1 <= target <= {0} 입니다. target = {1}", n, target);
                    throw new IllegalArgumentException(errorMessage);
                }
                targets.add(target);
            }
            
            int answer = 0;
            
            for (Integer target : targets) {
                // 중앙인덱스와 비교값간의 차이
                answer += queueRotator.pollElementBy(target);
            }
            System.out.println(answer);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static class QueueRotator<T> {
        
        private final LinkedList<T> queue;
        
        public QueueRotator() {
            this.queue = new LinkedList<>();
        }
        
        private LinkedList<T> add(T element) {
            queue.add(element);
            return queue;
        }
        
        public int pollElementBy(T element) {
            Objects.requireNonNull(element, "element 는 null 이 될 수 없습니다.");
            // 타겟 값과 중앙값의 인덱스 차이비교하여 큐를 회전시킨다.
            boolean isMidIndexGreater = isMidIndexGreaterThanIndexOf(element);
            if (isMidIndexGreater) {
                return pollFirstUntilSame(element);
            }
            return pollLastUntilSame(element);
        }
        
        private int pollLastUntilSame(T element) {
							//NPE 방지 해야함 ㅇㅇ
            int affected = 0;
            while (true) {
                T last = queue.getLast();
                
                if (Objects.equals(last, element)) {
                    pollLast();
                    // 마지막 값을 제일 앞으로 보내는 동시에 값이 사라지기에, affected 를 1 증가시킨다.
                    affected++;
                    break;
                }
                pollLast();
                // 맨 앞으로 보낸다.
                addFirst(last);
                affected++;
            }
            return affected;
        }
        
        private int pollFirstUntilSame(T element) {
						//여기도 NPE 방지해야하긴함.
            int affected = 0;
            while (true) {
                T first = queue.getFirst();
                if (Objects.equals(first, element)) {
                    pollFirst();
                    break;
                }
                pollFirst();
                // 맨 뒤로 보낸다.
                addLast(first);
                affected++;
            }
            return affected;
        }
        
        private boolean isMidIndexGreaterThanIndexOf(T element) {
            Objects.requireNonNull(element, "element 는 null 이 될 수 없습니다.");
            int elementIndex = queue.indexOf(element);
            int midIndex = queue.size() / 2;
            return elementIndex <= midIndex;
        }
        
        private LinkedList<T> pollFirst() {
            queue.pollFirst();
            return queue;
        }
        
        private Queue<T> pollLast() {
            queue.pollLast();
            return queue;
        }
        
        private Queue<T> addFirst(T element) {
            queue.addFirst(element);
            return queue;
        }
        
        private Queue<T> addLast(T element) {
            queue.addLast(element);
            return queue;
        }
        
    }
    
}

• 너무 어렵게 푼거같다..

• 그냥 중앙인덱스 기준으로 오른쪽이면 오른쪽 큐값 제거제거
  • 오른쪽 값의 경우 별도로

• 왼쪽이면 왼쪽값 제거제거

• 카운트 리턴 이 끝이다.

---

클래스: QueueRotator

• pollElementBy: 타겟 요소를 찾아 큐에서 빼내는 데 필요한 회전 횟수를 반환합니다.

• isMidIndexGreaterThanIndexOf: 타겟 요소의 인덱스가 큐의 중간 인덱스보다 작거나 같은지 판단합니다.

• pollFirstUntilSame와 pollLastUntilSame: 타겟 요소를 찾을 때까지 큐를 앞 또는 뒤로 회전시킵니다.

Uploaded by N2T