[Codility] FrogRiverOne JavaScript

Sohyeon Bak·2021년 11월 29일

Codility

목록 보기

5/19

문제

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

function solution(X, A);

that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].

문제해석

개구리는 반대편 강으로 가고 싶은데 나무에서 떨어진 나뭇잎을 밟고 건너갈 수 있다. 건너편의 위치는 X이며 건너가기 위해서는 X의 나뭇잎이 떨어져야하고, X의 나뭇잎이 떨어졌다 해도 그 전에 해당하는 모든 나뭇잎이 있어야 움직일 수 있다.
즉, X=5 라면 배열에는 5가 있어야하고, 5 이전에 1부터 4까지의 나뭇잎이 존재해야 갈 수 있다.

문제풀이

이 문제는 Set을 이용해서 푼다면 효율적이고 간단하게 해결할 수 있다.

Set에 배열의 요소를 추가해 중복없이 값을 저장한다.
배열을 돌면서 X에 해당하는 값이 있고, Set의 길이가 X와 같다면 정답이고 그렇지 않고 배열이 끝난다면 -1을 출력해준다.

코드

function solution(X, A) {
    let answer = -1;
    let tmp = new Set();

    for(let i = 0; i<A.length; i++){
        tmp.add(A[i]);
        if(tmp.size===X) return answer = i
    }

    return answer
}