Codility - Frog River One

Frog River One

문제

개구리가 X 까지 가고 싶은데, X까지 가기 위해서는 1부터 X를 모두 지나가야 한다. 예를 들어보자.

이렇게 배열이 주어져 있고

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

5까지 가고 싶다고 가정했을때, A[6]까지는 1~5의 지점이 모두 존재하기 때문에 갈수 있으며, 해당 인덱스인 6을 리턴한다. 
하지만 갈 수 없을 경우 -1을 리턴하면 된다.

풀이

function solution(X, A) {
    
    // X 까지 가고 싶다면, 1~X 까지의 숫자가 모두 존재해야한다.
    let sum = (X * (X + 1)) / 2
    
    // 등장했던 숫자인지 아닌지 판별한다.
    // 이럴거면 굳이 Set을 안써도 되긴하네
    const appear = new Set()

    for (let i=0; i < A.length; i++) {    
        const target = A[i]
        
        // 전에 없던 숫자만
        if (!appear.has(target)) {
            // 숫자를 노출 목록(?) 에 더하고
            appear.add(target)

            // 합계에서 하나씩 뺸다
            sum -= target
            
            // 0 이 된다면 바로 그 index다
            if (sum === 0) {
                return i
            }

            // 만약 0 보다 작아진다면 이미 글러먹었으므로 리턴한다.
            if (sum < 0) {
              return -1
            }
        }
    }
    
    return -1
}

해설

배열 관련 문제가 나온다면 항상 최초 한번의 순회로 어떻게 잘 승부 볼 수 있을지 고민해보자

https://app.codility.com/demo/results/trainingKDYYTF-8AU/