24. Jolly Jumpers

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

 

 

문제 24

 

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

 

 

입력예제

 

5

1 4 2 3 7

 

 

출력예제

 

YES

 

---

 

내가 쓴 코드

 

#include <stdio.h>
using namespace std;
int cnt[100000];


int main(){
	//freopen("input.txt", "rt", stdin);
	int n, pre, now, cha, i, yes=0;
	
	scanf("%d", &n);
	scanf("%d", &pre);
	
	for(i=2; i<=n; i++){
		scanf("%d", &now);
		cha = now-pre;
		if(cha<0) cha=cha-cha*2;
		else cha; 
		
		cnt[cha]++;
		pre=now;
	}
	for(i=1; i<=n-1; i++){
		if(cnt[i]==1) yes+=1;
		else yes+=0;
	}
	if(yes==n-1) printf("YES");
	else printf("NO");
	
	return 0;
}

 

이전 차시에 활용했던 pre와 now개념을 활용해서 이 문제도 풀어보았다. 내가 pre와 now의 개념을 또 취한 이유는 바로 앞 뒤 두 수를 활용하는 것이 비슷했기에 똑같이 이 개념을 활용해서 풀었다. 

https://ts2ree.tistory.com/31 (23번 문제인 연속 부분 증가수열)

 

 

 

 

1. 먼저 맨 처음의 값을 pre의 값으로 scanf 해서 입력을 받는다.

2. 그 다음 n까지의 값들을 now 변수를 통해서 받는다. 이때 바로 앞 뒤 두 수의 차이를 절댓값으로 취해줘야 해서 if 문을 활용해서 절댓값으로 치환해준다.

3. cnt[cha]++ 는 예전에 풀었던 문제에서 또 아이디어를 가져왔다. 차이가 3 2 1 이런 식으로 될 것이기 때문에 cnt 배열의 각 자리에 1씩 카운트를 해주었다.

4. 다음은 for문을 이용해서 cnt 배열에서 1부터 n-1까지의 자리에서 1씩 존재할 때 yes라는 변수에 1을 더해주었으며, yes 변수에 n-1 합이 존재하면 유쾌한 점퍼임을 출력("YES")을 해준다.

 

 

 

 

※ 입력예제와 출력예제를 먼저 잘 살펴보면서 하면 시간이 오래 걸리지 않았을 텐데, 문제만 읽고 코드를 짰다가 n인지 n-1인지에서의 실수가 생겼었다. 예제를 잘보고 정확히 코드를 짜보는 습관을 기르자!

 

 

 

 

 

 

선생님이 작성한 코드

 

#include <stdio.h>
#include <vector>
#include <algorithm>    // abs 함수를 써주기 위해서 필요한 라이브러리

int main(){
	int i, n, pre, now, pos;
    
    scanf("%d", &n);
    vector<int> ch(n);
    
    scanf("%d", &pre);
    for(i=2; i<=n; i++){
    	scanf("%d", &now);
    	pos=abs(now-pre);
        if(pos>0 && pos<n && ch[pos]==0) ch[pos]++;
        else {
        		printf("NO\n");
                return 0;
              }
        pre=now;
        }
              
	printf("YES\n");
    return 0;
}

 

선생님이 말씀하시길, 내가 한 방법(두 수의 차 카운트를 배열에 집어넣고 for문을 이용해서 배열을 check해주는 것)은 별로 좋지 않은 코드라고 말씀하셨다. (뜨끔!) 아마도 한번에 for문에 숫자를 입력 받으면서 바로 처리하는 것이 더 좋은 코드인 것 같다고 생각된다.

 

 

 

 

 

선생님도 pre, now 의 변수를 활용해서 코드를 작성하셨다. 알고리즘을 살펴보면,

 

 

1. 먼저 pre 변수로 첫번째 숫자 입력 받기

2. 그 다음 now를 입력 받아서 두 수의 차를 abs 라는 함수로 절댓값 구해주기

3. 두 수의 차(pos)가 0보단 크고 n보단 작아야 함 (=즉, 범위에 속해 있어야 한다.)

4. 그리고 기존의 ch[pos]가 0인지 체크를 해준다. (중복이면 안되므로)

5. 조건이 모두 맞으면 ch[pos]를 하나 증가시켜준다.

6. if문의 조건이 맞지 않으면 졸리 점퍼가 아니므로 NO 를 출력하고 프로그램을 끝낸다. ( return 0; )

7. if문의 조건이 다 맞으면 졸리 점퍼가 맞으므로 YES 를 출력하고 프로그램을 끝낸다.

 

 

 

 

 

 

※ 이때, if문의 조건을 쓸 때 주의해야할 것이 있다. 순서를 바꿔 쓰면 오류가 난다.

만약에 if( ch[pos]==0 && pos>0 && pos<n ) 이렇게 쓴다면 1 4 2 3 9 라는 숫자가 있을 때 3과 9의 차는 6이다.

하지만 ch[6]==0은 있지 않은 인덱스(6)를 참조하면 프로그램에서 오류가 발생한다. (원래 배열의 크기는 5이므로..)