[알고리즘][C++] Jolly Jumpers

#include <stdio.h>
#include <vector>
//#include <cmath>
#include <algorithm>
using namespace std;

//int main(){ 
//	//freopen("input.txt", "rt", stdin);
//	int n, i; 
//	scanf("%d", &n);
//	vector<int> num(n);
//	vector<int> ch(n);
//	for(i=0; i<n; i++){
//		scanf("%d", &num[i]);
//	}
//	for(i=1; i<n; i++){
//		int k = abs(num[i]-num[i-1]);
//		if( k > n ) {
//			printf("NO");
//			return 0;
//		}
//		else {
//			ch[k]++;
//		}
//	}
//	for(i=1; i<=n; i++){
//		if(ch[i]==0){ //불필요한 배열 탐색!
//			printf("NO");
//			return 0;
//		}
//	}
//	printf("YES");
//	
//	return 0;
//}

int main(){ 
	//freopen("input.txt", "rt", stdin);
	int n, i, pre, now, pos; 
	scanf("%d", &n);
	vector<int> ch(n);
	scanf("%d", &pre);
	for(i=1; i<n; i++){
		scanf("%d", &now);
		pos=abs(pre-now);
		if(pos>0 && pos<n && ch[pos]==0) ch[pos]=1;
		else {
			printf("NO");
			return 0;
		}
		pre=now;
	}
	printf("YES");
	
	return 0;
}

 

1 ~ n-1까지 값을 모두 가지고 있는지 확인하기 위해서 

 

ch 배열을 생성해서 마지막에 하나하나 검사하는 방식으로 코드를 작성 

 

-> 비효율적! 

 

1 ~ n-1 범위에서 해당 값을 모두 가지고 있으려면 중복되는 값이 있으면 안된다 

 

== ch배열에 들어 있는 값이 1 이라면 이미 앞에서 해당 값이 나옴

 

-> 중복 !! (==1~n-1 값 중에 하나는 채울 수 없음)

 

-> jolly jumpers 아님 

 

 

 

이러한 원리를 이용하여 

 

ch[pos] == 0  조건을 넣은 것! 

 

(하지만 마지막 조건으로 넣어야 한다!!)

-> pos가 n 값보다 큰데 ch 배열에 넣으려고 하면 오류 발생 하기 때문에 1~n-1 범위 조건에서 미리 탈락 시키는 것