[Algorithm] MaxCounters

[hwangJi-dev]

💬 문제

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

💬 Idea

• maxCounter로 바꾸는 시점에서 Array(repeating:, count:) 메서드를 사용했더니 시간 초과가 발생했다.
• 시간 초과를 해결하기 위해 많은 시간이 걸렸다.. ㅠㅠ
• 해결 로직
  • increase: maxCounterValue보다 현재 counter가 작다면 counter를 maxCounterValue로 변경해주고 그 이후에 +1 작업을 수행한다.
  • maxcounter로 모두 변경 메서드: 반복문 이후에 일괄 수행한다.

💬 풀이

import Foundation

public func solution(N : Int, A : inout [Int]) -> [Int] {
    var counter = Array(repeating: 0, count: N)
    var maxCounter = 0
    var maxCounterValue = 0
    
    for a in A {
        if a == N + 1 {
            maxCounterValue = maxCounter
        } else {
            if counter[a - 1] < maxCounterValue {
                counter[a - 1] = maxCounterValue
            }
            
            counter[a - 1] += 1
            
            if maxCounter < counter[a - 1] {
                maxCounter = counter[a - 1]
            }
        }
    }
    
    for i in 0..<counter.count {
        if counter[i] < maxCounterValue {
            counter[i] = maxCounterValue
        }
    }
    
    return counter
}

소요시간 : 1시간

시간 복잡도 : O(N + M)

평가표 : https://app.codility.com/demo/results/trainingW968PA-XQX/