[Java] 배열 흔들기

1. 문제 설명

n개의 배열이 있을 때 두가지 기능을 구현하여 배열의 원소의 위치를 바꾸고자 한다

• 배열의 원소들을 모두 왼쪽으로 한 칸씩 옮긴다. 이때 0번은 n-1번으로 이동
• 배열의 원소들을 모두 오른쪽으로 한 칸씩 옮긴다. 이때 n-1번은 0번으로 이동
  ex) 1, 2, 3, 4, 5 (왼쪽으로 옮기면) -> 2, 3, 4, 5, 1

실제로는 위를 응용한 아래의 4가지 명령어를 구현한다

• 입력으로 0 P 가 주어지면 화면에 현재 배열의 P번 칸에 있는 원소를 한 줄에 출력해준다.
• 입력으로 1 K 가 주어지면 현재 배열을 왼쪽으로 한 칸씩 옮기는 동작을 총 K번 수행한다.
• 입력으로 2 K 가 주어지면 현재 배열을 오른쪽으로 한 칸씩 옮기는 동작을 총 K번 수행한다.
• 입력으로 3 이 주어지면 배열을 한 칸도 좌우로 이동하지 않았던 초기 상태로 되돌린다.

입력형식

첫 줄에는 배열의 크기 N과 처리할 명령어의 수 M이 공백으로 구분 된 두 자연수로 주어진다. N과 M은 모두 1,000이하의 자연수이다.

두 번째 줄에는 초기 배열에 존재하는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 배열의 모든 원소는 1,000이하의 자연수이다.

이후 총 M줄에 걸쳐서 한 줄에 하나씩 네 가지 명령어 중 하나가 주어진다.

각 명령어의 처리 방법은 문제 설명과 예시를 참고한다.
0 P 명령어에서 P는 0이상 (N-1)이하의 정수이다.
1 K, 2 K 명령어에서 K는 1만 이하의 자연수이다.

출력형식

입력으로 명령어 0 P 가 주어질 때 마다 배열의 P번 칸에 존재하는 원소를 한 줄에 출력한다.

2. 알고리즘 접근

이는 배열을 직접 움직이는 시뮬레이션 배열처럼 보이나,
WorstCase는 배열이 1000번 움직이는 명령어 1000개의 10000번의 명령어수
즉 직접 배열을 움직이지않고 배열의 시프트되었을 때 특정 위치의 원소를 구한다

만약 위 사진과 같이 인덱스가 순환하도록 배열들이 반복해서 나열됐다고 가정하자
만약 위와 같이 왼쪽으로 쉬프트한다면 1번째 인덱스 B가 첫번째가 될 것
`즉 배열이 왼쪽으로 이동하면 배열의 범위가 오른쪽으로 한칸 이동하는 것과 같다
ex) 이동한 첫원소의 인덱스가 [2]라면 -> 이동한 4번째 원소는 [2 + 4] 인덱스

3. 소스코드

import java.util.Scanner;

public class Q4G {
    static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt(); // 배열의 크기 n
        int m = sc.nextInt(); // 처리할 명령어의 수 m

        ShiftingArray<Integer> array = new ShiftingArray<>(n);
        for(int i = 0; i < n; i++){
            array.set(i, sc.nextInt()); // 배열 데이터 입력
        }

        // 명령어 처리
        for(int i = 0; i < m; i++){
            int cmd = sc.nextInt(); // 명령어 정보 확인
            if(cmd == 0){
                // 현재 배열의 p번 인덱스를 출력하라
                int p = sc.nextInt();
                int value = array.get(p);
                System.out.println(value);
            } else if (cmd == 1) {
                // 현재 배열을 k번 왼쪽으로 이동
                int k = sc.nextInt();
                array.shiftLeft(k);
            } else if (cmd == 2) {
                // 현재 배열을 k번 오른쪽으로 이동
                int k = sc.nextInt();
                array.shiftRight(k);
            }else if (cmd == 3){
                // 현재 배열을 최초의 위치로 복원
                array.initializePosition();
            }

        }
    }
}
class ShiftingArray<T>{
    private final T[] array; // 내부에 데이터를 저장할 배열
    public final int length; // 배열의 길이

    private int leftIndex; // 가장 왼쪽에 있는 원소의 원본 배열의 인덱스

    public ShiftingArray(int length){
        this.length = length;
        this.array = (T[]) (new Object[length]);
        this.leftIndex = 0;
    }

    public void shiftLeft(int times){
        // 배열을 왼쪽으로 이동하는 것은
        // 배열의 시작점이 오른쪽으로 이동하는 것과 같다
        times = times % length; // 인덱스 초과를 맞기위한 나머지연산
        leftIndex = (leftIndex + times) % length;
    }
    public void shiftRight(int times){
        // 배열 오른쪽 이동은 배열의 시작점이 왼쪽으로 이동하는 것과 같다
        times = times % length;
        leftIndex = (leftIndex - times + length) % length;
    }

    public T get(int index){
        int realIndex = (index + leftIndex) % length;
        return array[realIndex];
    }

    // 현재 배열에서 index위치의 원소를 value로 변경하는 함수
    public void set(int index, T value){
        int realIndex = (index + leftIndex) % length;
        array[realIndex] = value;
    }

    // 현재 배열의 모든 원소를 초기로 변환하기
    public void initializePosition(){
        leftIndex = 0;
    }
}