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

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

1부터 X 까지 모든 숫자가 하나씩 나오는 시간을 찾는 문제다.

 

첫번째 해결방식은 다음과같았다.

제공받은 배열 에서 0번쨰 인덱스부터 시작하여

X 보다 같거나 작은 값만 새로운 배열에 넣어준다.

크거나 이미 새로운 배열에 있는 값은 패스하고

만약 X = 4 이고 새로운 배열에 [1,2,3,4] 가들어가면 리턴해주는 방식이다.

 

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    var answer = -1
    var arr = [Int]()

    for i in 0..<A.count{
        if(A[i] <= X && !arr.contains(A[i])){
            arr.append(A[i])
        }
        if( arr.count >= X){
           answer = i
           break
        }
   
    }

    return answer
}

새로운 배열 arr 이 X 보다 작다면 -1이 리턴 될것이고 그렇지 않으면 마지막 i 가 리턴된다.

답은 맞췄지만 시간이 초과되는 문제가 발생했다.

 

 

 

 

 

구글링 결과 다른 정답을 찾았는데 큰 차이가 없었다.

set을 사용해서 중복을 방지했다고는 하지만 결국 A만큼 반복문을 돌린건 같고

값을 다찾으면 리턴하는 방식은 같았지만 이 해답은 O(N) 이 나왔다.

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    var existanceCheckSet = Set<Int>()
 
    for i in 1...X {
        existanceCheckSet.insert(i)
    }
 
    for (index, element) in A.enumerated() {
        existanceCheckSet.remove(element)
 
        if existanceCheckSet.count == 0 {
            return index
        }
    }
 
    return -1
}