[백준] 바구니 뒤집기 [C++, 코드, 어떻게 생각 했을까?]

구현

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

10811번: 바구니 뒤집기

 

코드

#include <iostream>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n, m;
	cin >> n >> m;

	int arr[101];
	for (int i = 0; i < n; i++) {
		arr[i+1] = i+1;
	}

	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		int count = end-start+1;

		for (int j = start; j < start+(count / 2); j++) {
			int tmp = arr[j];
			arr[j] = arr[end-j+start];
			arr[end-j+start] = tmp;
		}
	}

	for (int i = 1; i < n+1; i++ ) {
		cout << arr[i] << " ";
	}	
	
	return 0;
}

 

설명

 해당 문제는 브론즈 치고 범위 구하는 구간에서 많이 어렵지 않았나 싶었다. 왜냐하면 python 같이 reverse() 메서드가 있는 언어에서는 쉽게 reverse범위를 지정하고 사용할 수 있는데, c++ 같은 경우는 그게 아니다 보니 직접 구현해서 사용해야 했다. 그래서 구현하다 보니까 이게 바로 보일 때도 있고 이게 바로 보이지 않을 때도 있는 것 같다. 첫 번째 시도에서는 start 더해주는 걸 하지 못해서 답이 이상하게 나왔었는데 범위 체크를 다시 해보니 틀린 점을 바로 잡을 수 있었다. 하지만 앞서 언급했듯 해당 범위를 계산하는 문제는 연습을 참 많이 해야 하는 것 같다. 몇 번을 해도 익숙해지지 않는 느낌이다.

 

 문제에서 요구하는 것은 "범위가 주어졌을때 범위까지 역순으로 변경하는 것" 해당 문제의 요구사항이라고 볼 수 있다. 목적에 부합하기 위해서 해야 할 것은 아래와 같다.

 

 

범위가 주어졌을때 어떻게 바꿀 것인가?

swap을 많이 해보았다면 swap을 어떻게 응용할 수 있을 것인가?

범위를 구했다면 해당 범위를 모든 경우에 어떻게 적용할 수 있는가?

 

 

기본적으로 범위가 주어졌기 때문에 해당 범위까지만 역순으로 바꾸어 주면 되지만 구현은 생각보다 그렇게 간단하지 않다. 왜냐하면 범위가 항상 0부터 시작하는 게 아니기 때문에 배열을 많이 다뤄보지 않으면 이해하기 쉽지 않다고 생각한다. 차근차근 살펴보면 우선 start 시작범위는 항상 변한다. 그렇기 때문에 역순으로 출력하는 범위는 항상 변하며 공식도 달라져야 한다. 그럼 일단 기본적인 범위의 개수부터 구해주자. 범위의 개수라고 한다면 예를 들어 3, 5라면 start = 3, end = 5인 셈이다. 그랬을 때 5-3+1 = 3개의 수가 존재하는 것을 확인할 수 있다. 이 문제에서는 두 개의 원소끼리 위치를 바꾸라는 게 아니기 때문에 연속적인 범위에서 변경을 요구하고 있다. 범위에 몇 개의 수가 있는지 확인이 되었다면 이제 '역순'이 무엇일까를 생각해 보자. 역순이라는 건 단순하게 말하면 뒤에서부터 앞으로 나열되도록 만드는 것이다. 따라서 end -> start 순서대로 숫자를 나열하게 되면 그게 역방향으로 나열하게 된 것이다. 역순에 대해서 이해가 되었다면 이제 공통 패턴을 좀 생각해 볼 필요가 있다.

 

 

범위는 3, 5

i = 3, j = 5

i = 4

 

범위가 3, 6

i = 3, j = 6

i = 4, j = 5

 

 

 위에서 공통점이 한번에 보이지 않더라도 여기서도 천천히 분석해 보자. 우선 범위 안에 있는 수들의 개수가 짝수개일 때와, 홀수개일 때로 나뉠 수 있다. 그럼 일단 그렇게 분류해 보자. 그랬을 때 3 4 5라는 수열에 대해서 3개의 수를 역순으로 출력하게 되면 5 4 3 이 된다. 그럼 가만히 보면 가운데 4는 바뀌지 않아도 3, 5만 변경된 걸 확인할 수 있다. 그럼 여기서 가운데를 기준으로 변경해 볼 수 있다는 생각을 할 수 있을 것 같다. 다음으로 짝수개일 때를 확인해 보자. 3 4 5 6 총 4개의 숫자에 대해서 역순으로 출력하게 되면 6 5 4 3이 된다. 이때도 마찬가지로 2로 나눠서 절반이 되는 시점을 좀 살펴본다면 4가 된다. 그럼 4 이전까지의 숫자들을 끝에서부터 서로 바꿔볼 수 있지 않은가? 왜냐하면 3이 있어야 할 자리는 6이 왔고 4가 있어야 할 자리는 5가 왔기 때문이다. 그럼 위와 같은 사실로부터 절반의 범위를 통해 끝 숫자부터 하나씩 차례대로 자리를 체인지해주면 될 것 같다는 생각을 해 볼 수 있다.

 

 그럼 이제 위 범위를 조정해주는게 필요하다고 볼 수 있다. 왜냐하면 시작지점은 항상 바뀌기 때문에 절반으로 나눈 지점은 start부터 end범위 내에서 절반이어야 하기 때문이다. 어떤 경우라도 해당 범위 내에서 절반까지를 나타내어야 한다는 것을 알 수 있는데 그렇지 않으면 for문을 구성할 때 엉뚱한 곳에서 swap이 이루어지고 결국 답으로 이어지지 못하기 때문이다. 따라서 범위는 항상 start부터 시작해야 되니 start부터 개수만큼 떨어진 곳이 끝지점이 되기 때문에 start(end-start+1) 까지가 바로 swap을 진행할 범위가 되는 것이다. +1은 해당 끝 범위까지도 포함해야 되기 때문이다. 이것은 곧 start부터 end까지의 전체 범위를 나타낸다. 그럼 이제 swap의 패턴을 응용해 보면 되는데 우선 start의 지점이 매번 바뀔 수 있기 때문에 서로 스왑 할 위치도 즉 인덱스도 바뀌게 된다. 그래서 그러한 보정을 해주기 위해 끝에서 현재 start지점인 곳을 빼주고 거기에다가 start지점만큼 더해준다면 바꿔야 할 인덱스가 나오게 된다. 아래와 같이 나타내본다면.

 

 

i = 3, j = 6

i = 4, j = 5

 

i = 3, j = 6(end) - i(3) + start(3) = 6

i = 4, j = 6(end) - i(4) + start(3) = 5

 

 

 위와 같은 공식이 도출이 된다면 이제 swap할 대상에 대입만 해주게 된다면 정상적으로 스왑이 동작되는 걸 알 수 있다. 배열의 대한 이러한 계산적인 부분은 한 번에 쉽게 도출되는 건 아닌 것 같다는 개인적인 생각이다. 물론 잘하는 분들은 한 번에 보고도 감이 오겠지만 여러 번 검증 과정을 거치고 나서야 이해가 되는 나로서는 한 번에 도출되기 힘들다는 생각도 약간은 들었지만 그렇다고 시간소요가 큰 문제는 아니었다는 것이 내 결론이다.