[Codility(코딜리티)] Lesson4. FrogRiverOne (100%)

Lesson 4 Counting Elements - FrogRiverOne (Java Solution)

app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

FrogRiverOne coding task - Learn to Code - Codility

---

문제

작은 개구리가 강 건너편으로 건너기를 원한다

개구리는 처음에 0에 위치하고, X+1로 가기를 원한다

N개로 구성된 배열 A는 떨어지는 나뭇잎들을 나타내고,

A[K]는 K초에 한 나뭇잎의 위치를 나타낸다

목표는 1에서 X까지가는 가장 빠른 시간을 찾는 것이다

(즉, 1부터 X까지 모두 건너야한다)

 

예를들어,

X = 5, 

A = {1,3,1,4,2,3,5,4}

A[0] = 1 (1)

A[1] = 3 (1,3)

A[2] = 1 (1,3)

A[3] = 4 (1,3,4)

A[4] = 2 (1,2,3,4)

A[5] = 3 (1,2,3,4)

A[6] = 5 (1,2,3,4,5)

-> X =5까지 온 가장 빠른시간은 6초이다

A[7] = 4

즉, 정답은 6이다

만약 점프할 수 없다면 -1 이다 

 

해결

우선, A 배열의 요소는 1~X 사이의 값이다

배열을 돌면서 Set에 넣고,

Set의 Size가 X이면 해당 Index를 반환하면 된다

result의 기본값을 -1로 하여 해당되는 값이 없다면 -1을 리턴하도록 한다

public class FrogRiverOne {
    public int solution(int X, int[] A) {
        int result = -1;
        HashSet<Integer> set = new HashSet<>();
        for (int i=0; i<A.length; i++) {
            set.add(A[i]);
            if (set.size() == X) {
                result = i;
                break;
            }
        }
        return result;
    }
 }