[C언어 풀이] Codility - Lessons 4, (Counting Elements) FrogRiverOne

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제

 

 

설명

 

개구리의 위치는 0부터 시작합니다.

X값이 개구리가 가려는 지점의 길이 입니다.

 

X값이 5라고 가정한다면......

 

개구리 |                         강                           |도착지점

    |                                                       |

   0     |     .         .           .           .           .     |     

    |                                                       |

이런 식으로 되어 있고 개구리가 건너가기 위해선 각 지점마다 나뭇잎이 떨어져야 합니다.

 

 

개구리 |                         강                           |도착지점

    |                                                       |

   0     |    1         2          3          4         5     |     

    |                                                       |

 

 

강에 떨어지는 낙옆의 순서는 랜덤이고 중복이 될 수 있습니다. 

문재의 예시를 풀어 쓰자면

 

A[0] = 1    <<- 첫번째 낙옆 떨어짐     A[1] = 3    <<- 세번째 낙옆 떨어짐 A[2] = 1    <<- 첫번째 낙옆 2번 떨어짐(중복) A[3] = 5    <<- 다섯번째 낙옆 떨어짐 A[4] = 2    <<- 두번째 낙옆 떨이짐

A[5] = 3    <<- 세번째 낙옆 2번 떨어짐(중복) A[6] = 4    <<- 네번째 낙옆 떨어짐 ( 1~5까지 낙옆이 모두 채워 졌음으로 A[]의 index 값인 6을 반환) A[7] = 1

 

 

즉, 순열이 모두 채워지면 해당 index값을 반환하면 됩니다.

만약, 낙옆으로 길이 만들어지지 못한다면..... 즉, 순열이 만족하지 않는다면!

return -1을 하면 됩니다.

 

 

 

 

 

결과

 

https://app.codility.com/demo/results/trainingJ7HNH4-FNT/

 

 

 

 

소스코드

int solution(int X, int A[], int N) {
    // write your code in C99 (gcc 6.2.0)
    int i, sum, quo, ren;
    int temp[X];
     
    for(i = 0; i <= X; i++)
        temp[i] = i;
         
    sum = X + 1;   
    quo = X / 2;
    ren = X % 2;
     
    if(ren == 0)
        sum = sum * quo;
    else
        sum = (sum * quo) + quo + 1;
         
         
    for(i = 0; i < N; i++){
        if(temp[A[i]] == A[i]){
            sum -= temp[A[i]];
            temp[A[i]] = 0;
        }
        if(sum == 0)
            return i;
    }
     
    return -1;
}​

 

문제를 풀면서 문제를 이해하는데도 시간이 좀 걸렸습니다.

다 푸는데 20분정도 소요된것 같습니다.

 

저는 순열에서 중복값을 없에기 위해 'temp[]' 라는 배열을 만들고 'X' 값 만큼

'for문' 을 돌려서 숫자를 체운 후 'A[]' 배열과 비교하면서 중복값을 걸러냈습니다.

 

그뒤 X 값에 대한 순열의 합에서 차근차근 뺄샘을 하고 sum이 0이 되는순간 return 하는 식으로 만들었습니다.