[Swift] MaxCounters 문제 풀이 [Codility - Lesson4. Counting Elements]

💬 문제

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

MaxCounters coding task - Learn to Code - Codility

 

---

💬 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
}

 

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

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

Test results - Codility

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Codility/Counting%20Elements/MaxCounters.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift