BOJ)2505 두 번 뒤집기

문제 : https://www.acmicpc.net/problem/2505

ㄱ.arr배열에서 i번째의 위치에 있어야할 value는 i이다. (1<= i <= 10000)

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]
6	7	8	2	1	5	4	3	9	10
start				finish

만약 ㄱ.조건에 맞지않는 곳[1]이 있다면, 그 위치 [1]를 start, 그 위치에 원래 들어가야할 value(1)가 위치한 곳[3]을 finish라 본다.

start~finish까지 뒤집기를 실시하여 준 후, ㄱ. 조건에 합당한지 조사한다.

이 과정은 [1]에서 부터 순차적으로 실시되며, 2번의 뒤집기 내에 전부 실시된다.

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]
1	2	6	7	8	5	4	3	9	10
		start					finish

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]
1	2	3	4	5	6	7	8	9	10

만약 순차적으로 진행하였음에도 나오지 않을 경우, 역으로 뒤에서 부터 실시하여본다.

또한, 이 문제는 예외 처리를 잘해주어야 한다.

1. 뒤집기가 0번 일어나는 경우 

input

10

1 2 3 4 5 6 7 8 9 10 

output

1 1

1 1

2. 뒤집기가 1번 일어나는 경우

input

10

1 2 3 6 5 4 7 8 9 10

output

1 1 

4 6

3. 뒤집기가 2번 일어나는 경우

input

10

6 7 8 2 1 5 4 3 9 10

output

1 5

3 8

아마 1, 2번의 경우를 제외하고 코딩하면 76% 정도에서 틀렸다는 문구가 뜨게 될 것이다.

1번과 2번 경우를 추가하지 않아 꽤 오래 헤맸다.

#include <iostream> #include <algorithm> #include <vector> using namespace std; int n; int arr[10001] = { 0 }; int tmp[10001] = { 0 }; vector <pair<int, int>> res; void turn(int start, int finish) { int tmp = 0; for (int i = start, j = 0; i <= (int) (start + finish )/ 2; i++, j++) { tmp = arr[i]; arr[i] = arr[finish - j]; arr[finish - j] = tmp; } } bool check() { for (int i = 1; i <= n; i++) { if (arr[i] != i) return false; } return true; } int main(){ cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; tmp[i] = arr[i]; } int cnt = 0; int start = 0, finish = 0; //--처음부터 탐색하여 뒤집기 --// for (int i = 1; i <= n; i++) { if (arr[i] != i) { start = i; for (int j = i; j <= n; j++) { if (arr[j] == start) { finish = j; break; } } } if (start != 0) { cnt++; turn(start, finish); res.push_back(make_pair(start, finish)); start = 0; finish = 0; } if (check() == true && res.size() > 0) { if (res.size() == 1) cout << 1 << ' ' << 1 << "\n"; for (auto i : res) { cout << i.first << ' ' << i.second << "\n"; } return 0; } if (cnt == 2) break; } //--뒤에 부터 탐색하여 뒤집기 --// start = 0; finish = 0; cnt = 0; res.clear(); for (int i = 1; i <= n; i++) { arr[i] = tmp[i]; } for (int i = n; i >= 1; i--) { if (arr[i] != i) { finish = i; for (int j = 1; j <= n; j++) { if (arr[j] == finish) { start = j; break; } } } if (finish != 0) { cnt++; turn(start, finish); res.push_back(make_pair(start, finish)); start = 0; finish = 0; } if (check() == true && res.size() > 0) { if (res.size() == 1) cout << 1 << ' ' << 1 << "\n"; for (auto i : res) { cout << i.first << ' ' << i.second << "\n"; } return 0; } } if (cnt == 0) { cout << 1 << ' ' << 1 << "\n" << 1 << ' ' << 1 << "\n"; } }