[Inflearn] Jolly Jumpers

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 아래 수열이 입력되었다고 해보자.

      N = 5

      1 4 2 3 7 

      서로 인접해 있는 두 수의 차가 1에서 N-1까지 값을 모두 가지면 그 수열을 Jolly Jumper 라고 부른다고 했다.

      주어진 수열의 앞 뒤 숫자 차 절대값이 3, 2, 1, 4 이므로 1 부터 N-1까지 값을 모두 가진다.

      이렇게 이 수열은 유쾌한 점퍼가 되는 것이다.

      이 문제를 해결하기 위해서는

       - 인접한 두 수의 차를 구하는 단계

       - 차의 절대값을 저장하는 공간

       - 1 ~ N-1 까지 값이 모두 있는지 확인하는 단계

       가 필요할 것 같다. 

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <cstdio> #include <vector>   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, pre, now;          scanf("%d", &n);       std::vector<int> v(n);       scanf("%d", &pre);       for (i = 1; i < n; i++)     {         scanf("%d", &now);           v[abs(now - pre)]++;           pre = now;     }       bool isJumper = true;       for (i = 1; i < n - 1; i++)     {         if (v[i] != 1)         {             isJumper = false;                      break;         }     }       if (isJumper)         printf("YES\n");     else         printf("NO\n");       return 0; }

cs

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, i, now, pre, 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\n");
 
            return 0;
        }
 
        pre=now;
    }
 
    printf("YES\n");
 
    return 0;
}

반례를 생각해내지 못 했다.. 

1 ~ N-1 사이의 숫자가 나오지 않을 경우도 생각해서 그럴 때는 vector를 참조하지 않고 바로 No를 출력하고 종료하도록 설계했어야 했는데.. 이러한 반례의 testcase가 있었다면 vector의 엑세스오류가 나도 말았을 것이다.

그리고 for 문을 돌면서 1 ~ N-1 사이의 숫자가 모두 포함되었는지 확인할 필요가 없었다.

차의 절대값을 저장하는 과정에서 이미 전에 나온 차의 절대값이 또 나왔을 때 No를 출력하도록 하면 더 좋았을텐데 거기까지는 생각해내지 못 했다,,흑

결국, 또 한 번의 반복문으로 해결할 수 있던 문제를 두 번의 반복문을 사용하여 해결해버린 것이었던 것이었다..

3 5 4 2 7 을 예로 들면

index 1, 2 : 차의 절대값은 2

index 2, 3 : 차의 절대값은 1

index 3, 4 : 차의 절대값은 2 -> 참조 index의 원소가 0이 아닐 경우, 여기서 No를 출력하고 종료시키도록 설계

index 4, 5 : 차의 절대값은 5 -> 절대값의 차가 1 ~ N-1 의 범위에 들어오지 않을 경우, 마찬가지로 No를 출력하고 종료

+ vector을 동적으로 생성하면 기본적으로 원소를 0으로 초기화!

#. Result

  - Input --------------------------------------------------------

5

1 4 2 3 7

------------------------------------------------------------------

  - Output --------------------------------------------------------

YES

------------------------------------------------------------------