[Codility - Counting Elements] frog_river_one

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

FrogRiverOne coding task - Learn to Code - Codility

 

- array의 최대 사이즈는 100,000이므로, O(NlogN) 이하로 알고리즘을 구현해야 한다.

- Map을 사용해서 Hash로 구현을 한다. leaf의 위치를 key로 한다.

function solution(X, A) {
    let hashMap = new Map()
    let numOfLeaves = 0
    for(let i = 0; i < A.length; i++){
        if(hashMap.has(A[i])) continue
        else {
            hashMap.set(A[i], 1)
            numOfLeaves++
        }
        if(numOfLeaves === X) return i
    }
    return -1
}

 

- leaf가 이미 해당 위치에 존재한다면, 바로 다음 element를 탐색한다. 존재하지 않는다면, 해당 위치를 key로 하는 새로운 값을 hash에 setting한다. 동시에 leaves의 갯수를 +1 해주고, leaves가 X와 같아진다면 모든 필요한 나뭇잎들이 위치 해 있는 것이므로 이 때의 i를 반환해준다.

 

- 모든 element를 탐색했는데도 필요한 leaves의 갯수를 만족하지 못하면, 건너지 못하는 것이므로 -1을 return한다.