[Lesson 2] - 2. FrogRiverOne

Author : 프로 노마드 / Date : 2015.06.11 13:41 / Category : Programming/Codility

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

접근방법 :  도착지점인 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

소스 :  
// 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/)


저작자 표시 비영리 동일 조건 변경 허락
신고

'Programming > Codility' 카테고리의 다른 글

[Lesson 2] - 2. FrogRiverOne  (1) 2015.06.11
[Lesson 2] - 1. PermCheck  (0) 2015.06.10
[Lesson 1] - 3. TapeEquilibrium  (0) 2015.06.08
[Lesson 1] - 2. PermMissingElem  (0) 2015.06.08
[Lesson 1] - 1. FrogJmp  (0) 2015.06.08
Codility!!  (0) 2015.06.07

Tags : , , , , , , , ,

Trackbacks 0 / Comments 1

Copyright © 프로 노마드 All Rights Reserved
Designed by CMSFactory.NET