Codility Lesson4 - FrogRiverOne

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.

작은 개구리는 강의 반대편으로 가고 싶어합니다. 개구리는 처음에 강의 한쪽 둑(위치 0)에 위치하고 반대쪽 둑(위치 X+1)으로 가고 싶어합니다. 나뭇잎이 나무에서 강의 표면으로 떨어집니다.

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.

낙엽을 나타내는 N개의 정수로 구성된 배열 A가 주어집니다. A[K]는 K 시간에 한 잎이 떨어지는 위치를 나타내며 초 단위로 측정됩니다.

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.

목표는 개구리가 강의 반대편으로 점프할 수 있는 가장 이른 시간을 찾는 것입니다. 개구리는 1에서 X까지 강을 가로지르는 모든 위치에 잎이 나타날 때만 건너갈 수 있습니다(즉, 1에서 X까지의 모든 위치가 잎에 의해 덮여 있는 가장 이른 순간을 찾고자 합니다). 당신은 강에 흐르는 물의 속도가 무시할 정도로 작다고 가정할 수 있습니다. 즉, 나뭇잎이 강에 떨어지면 위치가 변하지 않습니다.

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

예를 들어, 다음과 같은 정수 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
In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

두 번째 6에서는 잎이 5번 위치에 떨어집니다. 이는 강 건너 모든 위치에 잎이 나타나는 가장 빠른 시기입니다.

Write a function:

class Solution { public int solution(int X, int[] 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.

N개의 정수와 정수 X로 구성된 비어 있지 않은 배열 A가 주어지면 개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 반환합니다.

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

개구리가 강 반대편으로 점프할 수 없다면 함수는 -1로 되돌아가야 합니다.  ✔✔

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

예를 들어, 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
the function should return 6, as explained above.

함수는 위에서 설명한 대로 6을 반환해야 합니다.

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].

N과 X는 [1..100,000] 범위 내의 정수입니다;
배열 A의 각 요소는 [1...X] 범위 내의 정수입니다.

---

2023.08.21

class Solution {
    public int solution(int X, int[] A) {
        int[] N = new int[X];
        for(int i = 0; i < X; i++) {
            for(int j = 0; j < A.length; j++) {
                if(A[j] == i+1) {
                    N[i] = j;
                    break;
                } else {
                    if(j == A.length - 1) {
                        return -1;
                    }
                }
            }
        }
        return Arrays.stream(N).max().getAsInt();
    }
}

 - TimeOut