[Swift 알고리즘] MaxCounters - Codility

MaxCounters coding task - Learn to Code - Codility

---

요약

88 → 100

효율성 문제로 조금 고민했던 문제이다.

최초 풀이에서는 max counter 연산 때, 새로운 배열을 만들어서 전달했는데,

Array() 생성의 시간복잡도는 O(N)이었다.

그도 그럴 것이, 배열의 길이만큼 메모리를 한 칸씩 이동하며 초기화 해주어야 하니까.

수정한 접근 방법에서, 변수를 따로 관리해야 하는 이유를 잠시 고민했다.

maxValue 값을 추적하는 시점과, 값을 갱신하는 시점이 달라야 하기 때문에, 2개의 변수(maxValue, maxTmp)를 사용해야 한다.

접근

최초 접근

// 문제 분석
// A 배열은 명령어를 원소를 갖는다. (원소의 개수는 M, 랜덤이다)
    // 해당 명령어는 N개의 카운터에 대한 명령어의 집합이다.
    // A 배열의 원소(명령어)는 1...N+1 범위에서 정해진다
    // 1) 1...N은 해당 인덱스에 += 1
    // 2) N+1은 전체 카운터를, 현재의 max 값으로
// 카운터에 모든 명령어를 적용하고, 카운터에의 최종 형태를 return 한다.

// 접근법 분석
// N과 M은 각각 100,000이다
// O(N * M)은 시간 초과가 날 듯
// 간단한 방법은 A 배열을 탐색하며, 카운터 배열을 수정하는 방법이다.
    // maxValue를 따로 관리하고, 2) 명령어를 수행할 때, 배열 전체를 교체하는 방법을 쓰면,

수정한 접근

// 연산을 다르게 접근하자
// increase: 현재 인덱스의 값을 maxValue로 갱신한 뒤에, += 1, maxTmp를 갱신
    // 해당 연산에서 maxTmp를 갱신해야, 시간의 낭비가 없음
// max counter: maxValue 값을 maxTmp로 갱신함
    // 변수를 따로 관리하는 이유.
    // 가장 큰 값에 대한 추적을 사실상 increase 연산에서 하고 있으므로, 
    // max counter 연산이 수행될 때에만 maxValue 값을 업데이트 하고 싶으면, 
    // 변수를 따로 관리해야 함.

최초 풀이

import Foundation
import Glibc

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var counter = Array(repeating: 0 , count: N)
    var maxValue = 0
    
    for operation in A {
        switch operation {
            case 1...N:
                counter[operation - 1] += 1
                let currentIdxValue = counter[operation - 1]
                if currentIdxValue > maxValue {
                    maxValue += 1
                }
            default: // N + 1
                counter = Array(repeating: maxValue, count: N)
        }
    }

    return counter
}

수정한 풀이

import Foundation
import Glibc

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var counter = Array(repeating: 0, count: N)
    var maxValue = 0, maxTmp = 0

    for operation in A {
        switch operation {
            case N + 1:
                maxValue = maxTmp
            default:
                counter[operation - 1] = max(maxValue, counter[operation - 1]) + 1
                maxTmp = max(counter[operation - 1], maxTmp)
        }
    }

    for (idx, elem) in counter.enumerated() {
        counter[idx] = max(elem, maxValue)
    }

    return counter
}