Codility - MaxCounters

app.codility.com/programmers/lessons/4-counting_elements/

4. Counting Elements lesson - Learn to Code - Codility

문제

• 마지막 카운터의 배열을 반환하라

조건

• counter(X) -> arr[k] <= N -> K번째 1증가.

• max Counter -> arr[k] == N+1 -> 모든 카운터 Max값

풀이

• Arr[N] 개 만든다.

• A[K] <= N 이면 K-1 index 에 있는 Arr[k-1]++

• 이 때 Max값을 가지고 있는다.

• A[K] == N+1 Max값으로 변환

• A.count 만큼 실행

import Foundation
import Glibc

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    // - Arr[N] 개 만든다.
    var resultArr = Array<Int>(repeating: 0, count: N)
    var maxValue = 0
    // - A[K] <= N 이면 K-1 index 에 있는 Arr[k-1]++
    A.forEach { item in
        let index = item-1
        if index < N {
            resultArr[index] += 1
            if maxValue < resultArr[index] {
                maxValue = resultArr[index]
            }
        } else {
            resultArr = resultArr.map { _ in maxValue }
        }
    }

    return resultArr
}

실행시간 O(N*M)

---

실행시간이 커 제한된 시간 내에 들어오지 못하였다.

따라서 시간을 줄일 방법을 모색하였다.

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    // - Arr[N] 개 만든다.
    var resultArr = Array<Int>(repeating: 0, count: N)
    var maxValue = 0
    var baseValue = 0
    // - A[K] <= N 이면 K-1 index 에 있는 Arr[k-1]++
    A.forEach { item in
        let index = item-1
        if index < N {
            if resultArr[index] < baseValue {
                resultArr[index] = baseValue + 1
            } else {
                resultArr[index] += 1
            }

            if maxValue < resultArr[index] {
                maxValue = resultArr[index]
            }
        } else {
            baseValue = maxValue
        }
    }

    resultArr = resultArr.map {
        if $0 < baseValue {
            return baseValue
        } else {
            return $0
        }
    }

    return resultArr
}

A[K] == N+1 일 때 모든 Value를 바꿔주었는데 이 부분을 하지않고 baseValue를 두어 이를 해결 하였다.

실행시간 O(N+M) 이 되어 100점을 받을 수 있었다.