[BOJ/20127] Y-수열, C++

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

20127번: Y-수열

한줄 후기 : 내 코드의 반의 반 길이로 짠 사람을 봤을때 충격이란?

하.. 6번만에 AC 받았다. 실버 1 인데 고려할 케이스가 너무 많아서 찾느라 힘들었다.

눙물

k개만큼 앞에서 뒤로 이동시켰을 때, 전체가 증가 or 감소 수열이 되면 된다.

 

접근한 방법은

1. 처음 들어온 수열 자체가 증가, 감소 수열인지 확인

(처음 2개로 증가/감소 판별하고, 뒤이어 들어오는 수들 각각 비교해서 카운팅해줬다. 카운팅 된 개수가 N과 같다면 k=0 출력)

2. 원소 1개일 시 바로 k=0 출력

3. 만약 같은 원소가 있을 시 1번에선 증가수열만 체크돼서 감소 수열을 따로 체크해준다. (ex. 5 5 4 4 3)

4. 첫번째 원소와 마지막 원소 크기 비교 후 증가수열로 만들지, 감소 수열로 만들지 체크해준다. 

5. searchIdx 함수에선 가장 처음으로 반전되는 index를 찾아준다. 

(예를 들어 3 5 6 1 2 면, 3 > 2 니까 증가 수열로 만들 것이고, 3 < 5 < 6 > 1 이니 가장 먼저 반전된 6~1 이 때, 1의 index 3을 찾는 것이다. 이유는 그 index 부터 시작해서 검사할 거라서)

6. 만약 첫번 째 원소와 마지막 원소 크기가 같다면 searchIdx 를 증가/감소 둘 다 탐색해서 더 앞쪽 index로 선택한다.  그 이유는 index가 결국 k가 될거라서 더 작은 k를 선택해야한다는 문제의 조건 때문이다.

7. index 부터 N까지 증가/감소 판별하고, 중간에 미리 정해둔 증가/감소가 달라진다면 바로 -1 출력

8. 7에서 무사히 통과했다면 이어서 0~index-1까지 검사 역시나 미리 정해둔 증가/감소가 달라진다면 바로 -1 출력

 

엄청난 경우가 존재했다.

특히나 1 1 2 2 이런 같은 원소가 있을 경우를 잘 생각을 못했어서 처음에 많이 틀렸던 것 같다.

어려워!

//AC
//BOJ 20127 Y-수열
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int searchIdx(int N, int ck){
	int idx = 0;
	for(int i=0; i<N-1; i++){
		if(ck){
			if(v[i] < v[i+1]){
				idx = i+1;  //반전되는 index 찾기
				break;
			}
		}
		else{
			if(v[i] > v[i+1]){
				idx = i+1;  //반전되는 index 찾기
				break;
			}
		}
	}
	return idx;
}
int main(){
	int N, ck=0, idx = 0, cnt = 1, prev = 0;
	cin >> N;

	for(int i=0; i<N; i++){
		int n;
		scanf("%d", &n);
		v.push_back(n);
		if(i == 1){
			if(v[i] >= v[i-1]){
				prev = 0;  // 전체 수열 정렬 확인 - 증가 수열
				cnt++;
			}
			else if(v[i] <= v[i-1]){
				prev = 1;  // 감소 수열
				cnt++;
			}
		}
		else if(i > 1){
			if(v[i] >= v[i-1] && !prev) 	cnt++;
			else if(v[i] <= v[i-1] && prev)	cnt++;  // 0 - 1 비교 결과에 따라 카운트
		}
	}
	if(cnt == N || N == 1){   // 시작 수열이 증가 수열이거나 감소 수열이면 0, 원소 1개라면 0 출력
		printf("0");
		return 0;
	}
	cnt = 1;
	for(int i=1; i<N; i++){
		if(v[i] <= v[i-1])	cnt++;
	}   // 같은 것이 있는 감소 수열 검사 
	
	if(cnt == N){
		printf("0");
		return 0;
	}
	
	if(v[N-1] < v[0])	ck = 0;   // 증가 수열
	else if(v[N-1] > v[0]) 	ck = 1; 	// 감소 수열
	else{
		ck = 2;
		int fir = searchIdx(N, 0);
		int sec = searchIdx(N, 1);
		if(fir < sec){
			idx = fir;
			ck = 0;
		}
		else{
			idx = sec;
			ck = 1;
		}
	}
	if(ck == 0 || ck == 1){
		idx = searchIdx(N, ck);
	}
	
	if(ck){   // 감소 수열 확인
		for(int i=idx; i<N-1; i++){	
			if(v[i] < v[i+1]){
				printf("-1");
				return 0;
			}
		}		
		for(int i=0; i<idx-1; i++){
			if(v[i] < v[i+1]){
				printf("-1");
				return 0;
			}
		}
	}
	else {   // 증가 수열
		for(int i=idx; i<N-1; i++){
			if(v[i] > v[i+1]){
				printf("-1");
				return 0;
			}
		}
		for(int i=0; i<idx-1; i++){
			if(v[i] > v[i+1]){
				printf("-1");
				return 0;
			}
		}
	}
	printf("%d", idx);
	return 0;
}