FlogRiverOne 알고리즘

아래 문제는 코딜리티에서 제공하는 FlogRiverOne의 문제입니다🧑🏻‍💻

 

문제 제시

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:

public func solution(_ X : Int, _ A : inout [Int]) -> Int

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

 

문제 해결

import Foundation
import Glibc

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

 

사용된 개념

 - 배열 순회

 - enumerated

 

문제 뒷담화

해당 문제는 문제 풀이보다 문제 해석에서 시간이 오래걸렸다.

영어로 지문이 나오는 코딜리티다 보니 보통 간단한 문제라도 정확한 문제 이해에서 시간을 많이 뺏긴다.

우선 해당 문제의 요지는 X가 5로 주어지고 A에 떨어진 나뭇잎의 위치가 나온다.

개구리는 시작점인 0에서부터 도착점으로 주어진 X까지 건너가야한다.

건너가기위해 밟아야할 나뭇잎이 A 배열로 주어진다.

즉 X가 5이고 A의 배열이 들어올때 1~5까지의 Int가 A안에 다 들어있으면 건널수 있다.

1,2,1,2,5,3,4 처럼 들어올때 총 걸리는 시간은 7초이다.

즉 핵심은 나뭇잎의 배열을 돌면서 X보다 같거나 낮은 정수값이 다 포함되는 시점을 계산하는 알고리즘이였다.

그래서 enumerated 메서드를 활용하여 우선 index와 item을 알 수 있도록 하면서 조건문을 돈다.

그리고 나뭇잎은 중복되면 안되는 Set에 담아준다.

처음부터 접근하여 나뭇잎 정보를 담아주고 해당 나뭇잎 leaf Set 집합의 갯수가 주어진 X와 맞는 순간에 해당 index를 반환한다.

만약 아예 못건넌다면 요구하는 -1을 반환한다.

결국 이런 알고리즘으로 하면 최상의 O(n)의 시간복잡도를 가질 수 있다.

 

[풀이자료]

https://app.codility.com/c/run/trainingQUN8EF-W8N/

Codility