Codility - Lesson 4 MaxCounters

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

 

간략하게 말하면 N 사이즈의 Array B를 만들어서 A array의 항목들을 하나 하나 확인하면서 그 값 a가 a>=1  && a<=N으면 array B의 a번째의 값을 1증가하고 a = N+1이면  array B의 모든 항목을 1증가시키는 문제 입니다.

 

그래서 다음과 같이 작성하였습니다.

fun solution(N: Int, A: IntArray): IntArray {
    // write your code in Kotlin
    
    var ans = IntArray(N)
    var max = 0;
    for(i in A.indices){
        if(A[i] >= 1 && A[i] <= N){
            ans.set(A[i]-1,ans[A[i]-1]+1)
            if(max < ans[A[i]-1]){
                max =  ans[A[i]-1]
            }
        }else if(A[i] == (N+1)){
             for(j in ans.indices){
               ans.set(j,max)
             }
        }
    }
    return ans
}

그런데 결과는 88% 이유는 모든 값이 A의 모든 값들이 N+1일 경우 이중 for문이 되어 수행 시간이 길기 때문입니다.

 

그래서 다시 작성해보았습니다.

fun solution(N: Int, A: IntArray): IntArray {
    // write your code in Kotlin
    
    var ans = IntArray(N)
    var max = 0
    var position = 0
    var checkMax= 0;
    for(i in A.indices){
        if(A[i] >= 1 && A[i] <= N){
            if(ans[A[i]-1] < checkMax){
                ans[A[i]-1] = checkMax
            }
            ans[A[i]-1]++
            if(max < ans[A[i]-1]){
                max =  ans[A[i]-1]
            }
        }else if(A[i] == (N+1)){
            position = i
            checkMax = max
        }
    }
    if(position > 0){
        ans = IntArray(N,{checkMax})
        for(i in position+1 .. A.size-1){
            ans[A[i]-1]++
        }
    }
    return ans
}

A[K]가 N+1이 없을 경우와 이중 for문을 제거한 code 입니다. (해결하는데 약 1시간 반정도 걸렸네요)

Array A를 for문을 통하여 위의 문제 조건에 맞게 Array ans의 각각의 요소 값을 1씩 증가 시킵니다. 

그러다가 A[i]의 값이 N+1일 경우 그 position을 저장 하고 그때의 최대 값을 checkMax에 적용합니다.

그리고 계속 for문을 진행하는데 이때 checkMax의 값보다 ans[i]가 작다면 그 ans[i]의 값을 checkMax로 변경 후 위의 조건을 진행합니다. 이유는 A[i] == N+1이 되면 Array ans의 모든 요소가 최대 값으로 변경되기 때문입니다.

그래서 위의 정보를 토대로 모든요소가 checkMax인 Array ans를 다시 만들고, 아까 구한 position보다 1큰 위치에서 부터 다시 Array A를 확인하여 Array ans의 값들을 1씩 증가 시키고 return 합니다.

만약 N+1이 되는 값이 없다면 지금까지 증가시킨 값이 정답이므로 그대로 return 합니다.

 

설명이 어려워 보여서 제 로직을 위 문제에 나온 example로 ans 값을 보여드리겠습니다.

N= 5 Array A = {3,4,4,6,1,4,4} 이고

Array ans는 다음과 같이 변경 됩니다.

{0,0,0,0,0}

{0,0,1,0,0}

{0,0,1,1,0}

{0,0,1,2,0}

{0,0,1,2,0} position =3 checkMax = 2

{2,0,1,2,0} 되었다 -> {3,0,1,2,0}

{3,0,1,3,0}

{3,0,1,4,0}

 

for문이 끝나고 position이 0보다 크기 떄문에 Array ans는 {2,2,2,2,2}로 다시 생성되고

다시 Array A에 대해 for문을 진행하는데 position+1이므로 A[4]부터 진행됩니다. 그래서

{3,2,2,2,2}

{3,2,2,3,2}

{3,2,2,4,2}

가 되어 {3,2,2,4,2}를 return 합니다.