[Lesson 2] - 2. FrogRiverOne

문제 : 개구리가 강의 반대편으로 이동하는데 매 초마다 나뭇잎 한장이 떨어진다. 그 나무잎으로 점프해서 도착지점에 도달하는 가장 빠른 시간을 구한다.

접근방법 :  도착지점인 X의 값이 5라면 가장 빨리 도착할 수 있는 시간은 5초 이상의 값이 나와야만한다. (그래야만 길이 이어지기 때문이다)

                 이 문제도 순열 문제같다고 판단되서 PermCheck 문제와 같은 방법으로 접근. 

 먼저 새로운 배열로 나무잎이 떨어지는 곳을 순차적으로 표현하고,

                 시간이 X값과 같거나 커질경우, 배열을 검사하여 나뭇잎이 다 연결되어있는지 확인하는 방법으로 했다.

                 결국 중복 for문을 사용할 수 밖에 없게 되었다.  (https://codility.com/demo/results/demo6M2RXU-SWC/)

                중복 for문을 이용하지 않고 사용할 수 있는 방법은 없을까 고민하다가, 

                만약 X=5라면 도착 지점을 누적된 숫자로 표현하면 (1+2+3+4+5) = 15 가 된다는 것을 알았다.

                그래서 1~n의 총합을 구하는 등차수열의 합을 이용하여

                시간이 X값과 같거나 커질경우, 현재 배열의 수가 n(n+1)/2의 공식과 같은지 비교한 후 맞으면 return 하도록 구현하였다!

사용언어 : Javascript

소스 :  

123456789101112131415161718192021222324252627

// you can use console.log for debugging purposes, i.e.
// console.log('this is a debug message');

function solution(X, A) {
    // write your code in JavaScript (Node.js 0.12)
    var leafs = [];
    var N = A.length;
    var sum = 0;
    for (var i=0; i<N; i++) {
        leafs[i] = 0;
    }
    
    for (var T=0; T<N; T++) {
        if(leafs[A[T]-1]==0) {
            leafs[A[T]-1]++;
            sum=sum+A[T];
        }
        if(T>=(X-1)) {
            if (sum == (X*(X+1)/2)) {
                return T;
            }
        }    
    }
    
    return -1;

}

득점 :  100점 (https://codility.com/demo/results/demo5BQ83Q-TPQ/)