[algorithm] CodeUp # 4484 : 자물쇠

TToII·2021년 2월 19일
0

algorithm

목록 보기
4/5

CodeUp # 4484 : 자물쇠

사용 언어 : 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 함수 이용 방법을 다시 훑어보게 된 계기가 되었음 !

profile
Hello World!

0개의 댓글