[백준/BOJ] 10812번 바구니 순서 바꾸기 (C/C++)

백준 온라인 저지(BOJ) 10812번 바구니 순서 바꾸기
https://www.acmicpc.net/problem/10812

10812번: 바구니 순서 바꾸기

* 사용언어 : C언어, C++

 

1. 문제

1부터 N까지 번호가 새겨진 바구니를 M번 회전시킴
각 회전은 i부터 j까지 범위의 바구니를 k를 기준으로 회전시킴
M번 회전 후 왼쪽부터 모든 바구니를 출력

 

2. 풀이

배열의 index 를 자유자재로 다룰 수 있어야 쉽게 풀 수 있는 문제입니다.
우선 배열의 값을 유지하면서 변경할 수 없으므로 temp 배열을 하나 만들어서 값을 복사해둡니다.
그리고 temp 배열에 k 에 있는 값을 i 에 넣고, +1 해서 또 넣고
temp 배열의 index 가 j 가면 되면 i 로 돌아간 후 입력을 반복하면 됩니다.
 
위 방식을 머리로만 정리하여 구현해보니 계속 오답이 나왔습니다.
 
결국 각각의 케이스에 따라 i,  j,  k 를 직접 손으로 계산하며 시뮬레이션 해봤고
그 결과 배열의 index 를 어떻게 주면 되는지 구현할 수 있었습니다.
 
그렇게 for 문으로 구현한 코드는 아래와 같습니다.

scanf("%d %d %d", &i, &j, &k);

for (x = i; x <= j; ++x) t[x] = a[x];

for (x = k; x <= j; ++x) a[x - k + i] = t[x];
for (x = i; x < k; ++x) a[j - k + x + 1] = t[x];

 

이 코드도 정답이 되지만 설명하기도 어렵고 깔끔하지 않은 것 같아서 더 고민을 해봤습니다.
 
그러다가 index 를 어렵게 쓰지말고 처음에 설계한 그대로를 구현하면 되겠다는 생각을 했습니다.
즉, 값을 넣는 배열의 index(idxA) 와 값을 복사해둔 임시 배열의 index(idxT), 총 2개 index 를 동시에 사용하는 것 입니다.
그리고 그렇게 구현했더니 코드가 훨씬 깔끔해졌습니다.

(해당 코드는 아래 참고하시면 됩니다)
 
개인적으로 시뮬레이션 및 구현 유형의 문제는
하나 씩 직접 그려보면서 규칙을 이해한 뒤 구현하면 잘 풀린다는 교훈을 얻었습니다.

그리고 단순한 구현이 더 좋은 코드를 만든다는 것도 배울 수 있었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10812_바구니 순서 바꾸기
1116kb	0ms
*/
#include <cstdio>

const int LM = 101;
int a[LM], t[LM];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m;
	scanf("%d %d", &n, &m);

	int x;
	for (x = 1; x <= n; ++x) a[x] = x;

	int i, j, k;
	while (m--) {
		scanf("%d %d %d", &i, &j, &k);
		for (x = i; x <= j; ++x) t[x] = a[x];

		int idxA = i, idxT = k;
		while (1) {
			a[idxA++] = t[idxT++];
			if (idxT == j + 1) idxT = i;
			if (idxT == k) break;
		}
	}

	for (x = 1; x <= n; ++x) printf("%d ", a[x]);
	puts("");
	return 0;
}