문제

Find the earliest time when a frog can jump to the other side of a river.

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:

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.

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

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

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

풀이

예시

• 개구리가 처음 있는 위치는 index 0
• 목표는 5번째 칸까지 가는 것 (X = 5)
• Array의 index가 +1 되는 건 1초가 증가했다는 뜻

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4 

• 0초에는 나뭇잎이 1번째 칸에 떨어짐
• 1초에는 나뭇잎이 3번째 칸에 떨어짐
• ... 이를 그림으로 그려보면 아래와 같다.

파란거 개구리임

• 6초 일 때, 개구리가 X=5로 갈 수 있는 모든 칸이 채워짐

이를 코드로 표현해보면

public func solution_FrogRiverOne(_ X : Int, _ A : inout [Int]) -> Int {
    guard false == A.isEmpty else { return 0 }
    if 1 == X && 1 == A[0] {
        return 0
    }
    var leafs: Array<Int> = Array(repeating: 0, count: A.count)
    var count: Int = 0
    for index in 0...A.count-1 {
        let falledLeafPosition: Int = A[index]
        guard leafs.indices.contains(falledLeafPosition) else { continue }
        leafs[falledLeafPosition] += 1
        if 1 == leafs[falledLeafPosition] {
            count += 1
        }
        if X == count {
            return index
        }
    }
    return -1
}

• 예외상황(Array가 비어있거나, 1칸인데 나뭇잎이 이미 떨어져 있는 경우)을 제외
• 목표 count크기의 array를 생성
  • 1 채워질 때마다, count +1
  • 목표 칸만큼 counting되면 index를 return!

Tasks Details

• large permuation에서 error가 나는데, 왜그런지 잘 모르겠다 후움