[Swift] MaxCounters 문제 풀이 [Codility - Lesson4. Counting Elements]
💬 문제
https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/
MaxCounters coding task - Learn to Code - Codility
Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.
app.codility.com
💬 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
You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all counters are set to the maximum value of any counter. A non-empty array A of M integers is given. T
app.codility.com
GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift
Algorithm Practice with Swift. Contribute to hwangJi-dev/swiftAlgorithm development by creating an account on GitHub.
github.com