[백준] '바구니 순서 바꾸기' - Java

<문제 제시>

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 

도현이는 앞으로 M번 바구니의 순서를 회전시키려고 만들려고 한다. 도현이는 바구니의 순서를 회전시킬 때, 순서를 회전시킬 범위를 정하고, 그 범위 안에서 기준이 될 바구니를 선택한다. 도현이가 선택한 바구니의 범위가 begin, end이고, 기준이 되는 바구니를 mid라고 했을 때, begin, begin+1, ..., mid-1, mid, mid+1, ..., end-1, end 순서로 되어있는 바구니의 순서를 mid, mid+1, ..., end-1, end, begin, begin+1, ..., mid-1로 바꾸게 된다.

바구니의 순서를 어떻게 회전시킬지 주어졌을 때, M번 바구니의 순서를 회전시킨 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

---

<문제 해결 과정>

원래의 순서인 begin, begin + 1, mid - 1, mid, mid + 1, end - 1, end 를

기준이되는 mid에서부터 mid+1 ~ ... begin+1, mid-1 에 이르기까지의 순서로 회전시키면 되는 문제이다.

I 번째바구니부터 J 번째 바구니까지 회전시키고, 그 기준점은 K번째 바구니인 것이다.

---

<Try 1>

// 바구니의 개수 N
int N = Integer.parseInt(st.nextToken());

// 바구니를 회전시킬 횟수 M
int M = Integer.parseInt(st.nextToken());

// 기본 바구니 순서 선언 및 값 초기화
int[] basic = new int[N];
int k = 1;
for(int i = 0; i < N; i++) {
    basic[i] = k;
    k++;
}

System.out.println(Arrays.toString(basic));

int temp = 0; // 시작 인덱스의 해당하는 값을 저장하기 위한 변수
int data = 0; // 배열 갱신을 담당할 핵심 저장소

for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());

    // basic 배열로 갱신하고 길이는 똑같이 N만큼 확보
    int[] update = Arrays.copyOf(basic, N);

    // I번째 바구니부터 J번째 바구니의 순서를 회전시키는데,
    // 기준 바구니는 K번째 바구니
    int I = Integer.parseInt(st.nextToken()) - 1;
    int J = Integer.parseInt(st.nextToken()) - 1;
    int K = Integer.parseInt(st.nextToken()) - 1;

    // 시작인덱스를 끝인덱스 뒤에 붙여야하므로 변경 전 저장소에 임시 저장
    temp = basic[I]; 

    for(int j = I; j <= J; j++) {
        // 변경될 배열의 j번째(=K번쨰) 값을 basic[K]값으로 변경
        //System.out.println("현재 인덱스는 = " + j + " 입니다.");
        if(K <= J) {
            update[j] = basic[K++];
        }

        else {
            update[j] = basic[temp++] - 1;
        }

        System.out.println("변경된 배열 = " + Arrays.toString(update));

    }
    basic = Arrays.copyOf(update, N); // 회전한 배열로 기존 배열 갱신
}

첫번째 회전때는 정상완료되었지만, 두번째 회전부터 인덱스 범위 오류가 발생하였다.
>> 해결 필요

<Try 2>

// 바구니의 개수 N
int N = Integer.parseInt(st.nextToken());

// 바구니를 회전시킬 횟수 M
int M = Integer.parseInt(st.nextToken());

// 기본 바구니 순서 선언 및 값 초기화
int[] basic = new int[N];
int k = 1;
for(int i = 0; i < N; i++) {
    basic[i] = k;
    k++;
}

System.out.println(Arrays.toString(basic));

int temp = 0; // 시작 인덱스의 해당하는 값을 저장하기 위한 변수
int data = 0; // 배열 갱신을 담당할 핵심 저장소


for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());

    // I번째 바구니부터 J번째 바구니의 순서를 회전시키는데,
    // 기준 바구니는 K번째 바구니
    int I = Integer.parseInt(st.nextToken()) - 1;
    int J = Integer.parseInt(st.nextToken()) - 1;
    int K = Integer.parseInt(st.nextToken()) - 1;

    // 시작인덱스를 끝인덱스 뒤에 붙여야하므로 변경 전 저장소에 임시 저장
    temp = basic[I]; 

    int index = 0;
    int[] update = new int[(J - I) + 1];

    for(int j = I; j <= J; j++) {
        System.out.println(Arrays.toString(update));
        update[index++] = basic[j];
        System.out.println("변경된 배열 = " + Arrays.toString(update));
    }
    //System.out.println("변경된 배열 = " + Arrays.toString(update));
    // basic = Arrays.copyOf(update, N); // 회전한 배열로 기존 배열 갱신
}

basic (기존배열)에서 update(새로운배열)을 분할해내어 거기서 회전을 일으킨 후 기존배열에 다시 더해주는 방식을
취하고자했으나 잘 되지 않았다.

---

<Answer 1>

// 기본 바구니 순서 선언 및 값 초기화
// 처음부터 문제의 첫번째와 배열의 첫번째 인덱스 값이 다르므로 한 칸 더 확보
int[] basic = new int[N + 1];
int[] update = new int[N + 1];

// 각 배열 값 초기화 (대입)
// 여기서도 초기화 시 0번인덱스는 비우고 문제 상의 첫번째와 일치하도록 1번인덱스부터 값을 대입
for(int i = 1; i <= N; i++) {
    basic[i] = i;
    update[i] = i;
}

for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());

    // I번째 바구니부터 J번째 바구니의 순서를 회전시키는데,
    // 기준 바구니는 K번째 바구니
    int I = Integer.parseInt(st.nextToken());
    int J = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    // I 값 임시저장
    int I_init = I;

    for(int P = 0; P < J - I + 1; P++) {
        if(K + P <= J) update[P + I] = basic[K + P];

        else {
            update[P + I] = basic[I_init];
            I_init++;
        }
    }

    for(int P = 1; P <= N; P++) {
        basic[P] = update[P];
    }
}

---

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class q_10812_ChangeBK {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		// 바구니의 개수 N
		int N = Integer.parseInt(st.nextToken());
		
		// 바구니를 회전시킬 횟수 M
		int M = Integer.parseInt(st.nextToken());
		
		// 기본 바구니 순서 선언 및 값 초기화
		// 처음부터 문제의 첫번째와 배열의 첫번째 인덱스 값이 다르므로 한 칸 더 확보
		int[] basic = new int[N + 1];
		int[] update = new int[N + 1];
		
		// 각 배열 값 초기화 (대입)
		// 여기서도 초기화 시 0번인덱스는 비우고 문제 상의 첫번째와 일치하도록 1번인덱스부터 값을 대입
		for(int i = 1; i <= N; i++) {
			basic[i] = i;
			update[i] = i;
		}

		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			// I번째 바구니부터 J번째 바구니의 순서를 회전시키는데,
			// 기준 바구니는 K번째 바구니
			int I = Integer.parseInt(st.nextToken());
			int J = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			// I 값 임시저장
			int I_init = I;
			
			for(int P = 0; P < J - I + 1; P++) {
				if(K + P <= J) update[P + I] = basic[K + P];
				
				else {
					update[P + I] = basic[I_init];
					I_init++;
				}
			}
			
			for(int P = 1; P <= N; P++) {
				basic[P] = update[P];
			}
		}
		
		// 출력문
		for(int i = 1; i <= N; i++) {
			sb.append(update[i] + " ");
		}
		
		System.out.println(sb);
		
	}

}

---

기존 바구니 회전, 바꾸기 문제와는 다르게 난이도가 조금 있었다.

손으로 풀이해가면서 풀이해보는 과정이 필요한 문제였다.

---

<문제 링크>

https://www.acmicpc.net/problem/10812