[C/C++] 유쾌한 점퍼 (Jolly Jumper)

문제

N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을
모두 가지면 그 수열을 유쾌한 점퍼(jolly jumper)라고 부른다. 예를 들어 다음과 같은 수열에
서 1 4 2 3 앞 뒤에 있는 숫자 차의 절대 값이 각각 3 ,2, 1이므로 이 수열은 유쾌한 점퍼가
된다. 어떤 수열이 유쾌한 점퍼인지 판단할 수 있는 프로그램을 작성하라.

 

입력설명
첫 번째 줄에 자연수 N(3<=N<=100)이 주어진다.
그 다음 줄에 N개의 정수가 주어진다. 정수의 크기는 int 형 범위안에 있으며, 인접한 두 수의
차도 정수형 범위에 있습니다.
출력설명
유쾌한 점퍼이면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력한다.

문제풀이

유명한 문제라고 함. 우선 이 문제는 주요하게 두 가지 개념이 필요함.

첫 번째로, 범위를 벗어나는 경우 

두 번째로, 비둘기 집의 원리를 생각한다. 중복되는 경우의 수가 나오면, 모든 값을 만족할 수 없다는 것을 이용하는 것이다. N개의 정수가 주어지면 정확히 N-1개의 차가 발생한다. N-1개를 채워야하므로 하나라도 중복되면 모든 값을 채울 수가 없다.

 

어느 알고리즘 문제나 그렇겠지만 어떤 값을 입력받거나 할 때는 범위를 벗어나는 경우를 우선적으로 생각해야 한다. 그리고나서 이 외 따로 고려해야 하는 사항을 고려해야 한다.

 

아래 소스코드는 거의 기록용임.

 

1) vector를 사용하여 n개를 만들고 0번 인덱스를 제외한 n-1개 인덱스를 생성함.아래와 같이 만들 수 있음.

vector<int> v(n);

 

2) 범위를 확인하고 그 범위 안에 있다면 인덱스에 넣어 벡터 값을 바꿈.

if (diff>0 && diff<n && v[diff]==0) v[diff]=1;

short circuiting이라고 하여, 앞 조건이 맞지 않으면 그대로 false 처리한다. 따라서 diff가 예를 들어 인덱스보다 큰 값이 나오면, 앞에 diff<n 조건이 false이므로 그대로 if문이 false 처리됨.

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
	int n, pre, cur, diff;
	cin>>n;
	vector<int> v(n);
	cin>>pre;
	
	for (int i=1; i<n; i++)
	{
		cin>>cur;
		diff=abs(cur-pre);
		
		if (diff>0 && diff<n && v[diff]==0) v[diff]=1;
		else
		{
			cout<<"NO";
			return 0;
		}
		pre=cur;
	}
	
	cout<<"YES";
	
    return 0;
}

Reference

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비