[Algorithm] Codility Lesson 4 Counting Elements - FrogRiverOne

작은 개구리는 강의 반대편으로 가고 싶어 한다.

개구리는 처음에 강 둑 한 곳(위치 0)에 위치해 있고 반대쪽 둑(위치 X+1)으로 가고 싶어 한다.

잎들은 나무에서 강 표면으로 떨어진다.

떨어진 잎을 표현하는 N 개의 정수로 이루어진 배열 A가 주어진다.

A[K]는 K초에 떨어지는 잎의 위치를 표시한다.

목표는 개구리가 강의 반대편으로 점프할 수 있는 가장 빠른 시간을 찾는것이다.

개구리는 1부터 X 위치 까지 강을 건너는 동안 잎이 나타날 때만 이동할 수 있다.

(우리는 잎이 있는 위치만으로 1부터 X까지 이동하는 가장 빠른 시간을 찾기 원한다는 것이다.)

강에 있는 동안의 속도는 무시할 만큼 작다고 가정할 것이다.

즉 잎은 강에 떨어진 후에 위치가 변하지 않는다.

예를 들어 정수 X = 5 이고 배열 A가 다음과 같다면

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

6초에 잎이 위치 5에 떨어진다.

이것이 잎이 강을 가로 지르는 모든 위치에 나타나는 가장 빠른 시간이다.

함수 작성:

class Solution { public int solution(int X, int[] A); }

N개의 정수로 구성된 비어있지 않은 배열 A와 정수X가 주어지면

개구리가 강의 반대편으로 점프할 수 있는 가장 작은 시간을 리턴한다.

만약 개구리가 강의 반대편으로 점프할 수 없다면, 함수는 -1을 리턴해야 한다.

예를들어 정수 X = 5 이고 배열 A가 다음과 같다면

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

위에서 설명한 것처럼 함수는 6을 리턴해야한다.

가정 :

N 과 X는 [1..100,000] 범위의 정수;

A의 모든 요소는 [1..X] 범위의 정수이다.

복잡도 :

최악의 시간복잡도는 O(N);

최악의 공간복잡도는 O(X) (입력 공간 제외)

배열의 모든 요소는 수정 가능하다.

https://codility.com/demo/results/training9GNH47-G8Z/