8회차 - 배열 흔들기

 

 프로그래머 지수는 제비뽑기 프로그램을 만들고 있다. 자신이 이미 정해둔 N개의 배열에 각각 임의의 번호들을 저장해 두고 사용자들이 0~(N-1)의 정수 번호를 하나 입력하면 그 칸에 있는 숫자를 알려주게 된다. 하지만 자신의 제비뽑기 프로그램을 사람들이 사용하는 모습을 지켜보던 지수는 배열에 저장된 데이터들이 고정적이기 때문에 게임을 반복할 수록 사람들이 숫자를 추정할 수 있다는 문제점을 발견했다. 

그래서 지수는 아래와 같은 두 가지 기능을 구현하여 주기적으로 배열에 저장된 원소들의 위치들을 바꿔주고자 한다.

• 배열의 원소들을 모두 왼쪽으로 한 칸씩 옮긴다. 이 때 0번 칸에 있던 원소는 (N-1)번 칸으로 이동된다.
• 배열의 원소들을 모두 오른쪽으로 한 칸씩 옮긴다. 이 때 (N-1)번 칸에 있던 원소는 0번 칸으로 이동된다.

 

 하지만 위의 두 동작은 너무 단순하기 때문에 실제로는 위의 기능을 응용하여 아래와 같은 네 가지 명령어를 구현하고자 한다.

• 입력으로 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번 칸에 존재하는 원소를 한 줄에 출력한다.

 

import java.io.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int nNumbers = scanner.nextInt();   // 배열의 원소의 수
		int nCommands = scanner.nextInt();  // 처리할 명령어의 수

		// Shift 연산이 가능한 배열을 선언하고 원소를 차례로 입력한다
		ShiftingArray<Integer> array = new ShiftingArray<>(nNumbers);
		for(int i = 0 ; i < nNumbers ; i ++)
		{
			array.set(i, scanner.nextInt());
		}

		// 각 명령어를 처리한다
		for(int i = 0 ; i < nCommands; i+= 1)
		{
			// 명령어 정보를 입력받는다
			int cmd = scanner.nextInt();
			if( cmd == 0 )
			{   // 현재 배열에 p번 인덱스에 있는 원소를 출력하는 명령
				int p = scanner.nextInt();
				int value = array.get(p);
				System.out.println(value);
			}else if(cmd == 1)
			{   // 현재 배열을 왼쪽으로 k번 shift하는 명령
				int k = scanner.nextInt();
				array.shiftLeft(k);
			}else if(cmd == 2)
			{   // 현재 배열을 오른쪽으로 k번 shift하는 명령
				int k = scanner.nextInt();
				array.shiftRight(k);
			}else if(cmd == 3)
			{   // 현재 배열을 최초의 위치로 복원하는 명령
				array.initializePosition();
			}
		}
	}
}



class ShiftingArray <T> {

	private final T[] array;        // 내부에 데이터를 저장할 배열
	public final int length;       // 배열의 길이
	public int leftIndex; // 시프트 한 크기를 저장하는 변수

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

	/**
	 * 현재 배열에서 'index'번째에 존재하는 원소를 반환하는 함수
	 *
	 * @param index
	 * @return
	 */
	public T get(int index)
	{
		int realIndex = (index + leftIndex);
		return array[realIndex];
	}

	/**
	 * 현재 배열에서 'index'번째에 존재하는 원소를 'value'로 변경하는 함수
	 *
	 * @param index
	 * @param value
	 */
	public void set(int index, T value)
	{
		int realIndex = (index + leftIndex);
		array[realIndex] = value;
	}

	/**
	 * 현재 배열의 모든 원소를 왼쪽으로 'times'번 이동하는 함수
	 * @param times
	 */
	public void shiftLeft(int times){
		times = times % length;
		leftIndex = (leftIndex + times) % length;
	}

	/**
	 * 현재 배열의 모든 원소를 오른쪽으로 'times'번 이동하는 함수
	 *
	 * @param times
	 */
	public void shiftRight(int times){
		times = times % length;
		leftIndex = (leftIndex - times + length) % length;
	}

	/**
	 * 현재 배열의 모든 원소를 가장 초기 위치로 되돌리는 함수
	 */
	public void initializePosition()
	{
		leftIndex = 0;
	}

}