Codility Lesson 04 - FrogRiverOne( JAVA )

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

FrogRiverOne coding task - Learn to Code - Codility

 

문제

- 작은 개구리가 0위치에서 시작해서 X+1위치까지 건너가고 싶어한다.

- A 배열은 각 위치에 나뭇잎이 떨어지는 시간( second )를 나타낸다.

- 작은 개구리는 건너가고자 하는 모든 위치에 나뭇잎이 존재해야지만 건너갈 수 있다.

- 목표 위치까지 가장 빠르게 건널 수 있는 시간을 구해라.

 

제한조건

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

N과 X는 1 ~ 100,000 사이의 정수이다.

A의 각 원소는 1 ~ X 사이의 정수이다.

 

풀이

- answer = -1로 초기화 하고, 최소 시간이 나올 경우에는 answer값에 대입한다.

- road라는 임의의 boolean 배열을 선언하여 시간 때마다 떨어진 위치의 나뭇잎을 체크한다.

- road 배열에서 지나가지 않은 위치에 나뭇잎이 떨어질 때, cnt 변수를 +1하고, cnt변수와 (road배열의 크기 - 1)을 비교하여 체크한다.

 

참고 : 편의를 위해 road 배열은 X+1로 초기화 한다. ( index를 맞추기 위해서 )

 

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8
        boolean[] road = new boolean[X + 1];
        road[0] = true;
        int cnt = 0;
        int answer = -1;

        for( int i=0; i<A.length; i++ ){
            // 1. 위치에 나뭇잎이 존재하지 않는 경우
            if( !road[A[i]] ){
                road[A[i]] = true;
                cnt++;

                if( cnt == (road.length - 1) ){
                    answer = i;
                    break;
                }
            }else{
                continue;
            }
        }

        return answer;
    }
}