사용 언어 : c++
<풀이>
스페셜 져지 문제라서 테스트 케이스를 못본다 ..!!
그림 1에서 그림 4까지 도달하는 과정은 왼쪽으로 3 밀기 -> (7, 9)구간 뒤집기 -> 왼쪽으로 5 밀기이다
주어지는 테스트케이스 값은 3번의 과정을 수행한 후의 값이므로 역순으로 돌아가는 방법을 찾아 출력하면 된다
<처음 고민해본 방법>
1. 연속되는 최대 인덱스 길이를 찾아서 밀기
2. N과 N-1이 나오는 인덱스를 찾아서 범위 안의 값을 역순으로 돌리기
3. N이 위치한 인덱스 + 1 부터 배열의 최대 인덱스까지 카운트 값 출력
공개된 테스트 케이스 값으로 수행해본 결과는 통과했으나 잘못된 풀이...
계속 고민하다가 결국 구글링으로 능력자의 코드를 분석해보기로 했다
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
int main(){
int N;
cin >> N;
deque<int> lock(N);
int num;
for(int i = 0; i < N; i++)
cin >> lock[i];
int rotate2 = 0;
for(int i = 0; i < N; i++){
if(lock[N - 1] - lock[N - 2] != 1){
lock.push_front(lock.back());
lock.pop_back();
rotate2++;
}
else break;
}
if(rotate2 == 0) rotate2 = N;
// 마지막 원소 맨 앞에 넣기
lock.push_front(lock.back());
// 첫번째 원소를 맨 뒤에 넣기
lock.push_back(lock[1]); // 지금 deque에 있는 총 원소수는 N + 2
int tmp = 0;
int endIdx = -1;
for(int i = 1; i <= N; i++){
if(lock[i] - lock[i - 1] != 1 && lock[i + 1] - lock[i] != 1){
tmp++;
endIdx = i;
}
}
int startIdx = endIdx - tmp + 1;
reverse(lock.begin() + startIdx, lock.begin() + endIdx + 1);
int rotate1 = 0;
for(int i = 1; i <= N; i++){
if(lock[i] == 1){
rotate1 = N + 1 - i;
break;
}
}
cout << rotate1 << '\n';
cout << startIdx << ' ' << endIdx << '\n';
cout << rotate2;
return 0;
}
deque를 이용하여 이해하기 쉽게 풀어놓았다
1. 배열의 최대 인덱스, 최대 인덱스 -1 을 검사해 두 원소간 차가 1이 될 때까지 마지막 원소를 처음 원소로 이동시킨다 (rotate2++; 로 마지막 수행 횟수 출력 가능)
만약 처음부터 차가 1이 나온다면 맨 앞에 최대 인덱스 원소 추가, 맨 뒤에 최소 인덱스 원소를 추가해준다 (이 때, 원소의 개수는 N+2개)
2. 배열의 인덱스를 기준으로 -1 인덱스 +1 인덱스 와의 차가 모두 1이 아닌 경우 tmp값과 endIdx 값을 증가시키며 역순으로 뒤집을 구간을 찾아뒤집어준다
3. 원소가 1이 나오는 인덱스를 찾아 (N + 1 - i)를 통해 처음 수행 횟수를 찾는다
처음 생각한 방법도 deque를 이용하면 쉽게 풀 수 있을 거 같다..
deque 함수 이용 방법을 다시 훑어보게 된 계기가 되었음 !