Codility - Lesson4 FrogRiverOne

자세한 문제는 여기서 확인할 수 있습니다.

 

문제를 요약하자면 개구리가 X까지 가야하는데 주어진 Array에있는 값들이 1부터 X까지 순서대로 나열되는데 Array의 몇번째 항목까지 필요한가를  return 하는 항목입니다. 

주어진 example을 보면 X= 5이고 Array A는 A[0]=1 , A[1]=3 , A[2]=1 , A[3]=4 , A[4]=2 ,A[5]=3 ,A[6]=5 ,A[7]=4 일때 1,2,3,4,5를 만들기 위해서는 ArrayA의 A[6]까지 필요함으로 return 6이 된다는 의미 입니다. (문제 이해하는데 한 20분 쓴거 같네요)

 

그래서 해결 code는

fun solution(X: Int, A: IntArray): Int {
    // write your code in Kotlin
    var B = BooleanArray(X)
    var ans = 0;
    for( i in A.indices){
        if(B.size >= A[i] && !B[A[i]-1]){
            B.set(A[i]-1,true)
            if(ans < i)  ans = i
        }
    }
    
    for(i in B.indices){
        if(!B[i]) return -1
    }
    return ans
}

1. BooleanArray B를 X 사이즈 만큼 만들어 줍니다.

2. 그리고 A를 for문을 사용하여 각 항목을 확인하고 그 값을 보고 B의 그 값-1 위치를 true 변경합니다

ex) A[0] = 1이 므로 B[0]를 true 변경, A[1]=3이므로 B[2]=true로 변경

3. B의 항목에 적용할 때 A의 순서 i를 ans에 적용합니다. 왜냐하면 최종적으로 A의  몇번째 항목까지 필요한지를 알기 위해서 입니다.

4. 이 때 B의 항목이 이미 true면 패스 합니다.

5. 만일 B에 false가 1개 이상 있을 경우에는 순열이 아니므로 -1을 return 합니다.