[Swift 알고리즘] Codility - MaxCounters

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "Codility - MaxCounters" 문제를 풀었습니다.

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

MaxCounters coding task - Learn to Code - Codility

 

풀이

이번 문제는 O(N) 알고리즘으로 아래 두 개의 연산을 해야 하는 문제입니다.

• increase : 1 <= A[i] <= N 이라면 arr[i] += 1 을 합니다.
• maxCounter : A[i] > N 이라면 모든 원소에 arr.max( )를 대입합니다.

여기에서 해답 포인트는 maxCounter입니다.

maxCounter를 매 반복마다 해준다면 O(N^2) 혹은 O(N+M)이 됩니다.

저도 처음에는 O(N^2)으로, 두 번째는 O(N+M)이 되었는데요.

 

이것을 O(N)으로 해결하려면 마지막에 한 번만 처리를 해줘야 합니다.

즉, 매번 그때그때 처리하는 것이 아니라 후처리를 해야 한다는 의미입니다.

 

따라서 increase 연산을 할 때 최대값을 저장하고 maxCounter 연산을 해야할때 그 값을 저장해둡니다.

만약 increase 연산 시에 해당 원소 값이 마지막 maxCounter보다 작다면 그 값을 maxCounter값으로 대입하고 +1 을 합니다.

모든 counter 연산을 끝내고 마지막에 maxCounter보다 작은 값을 maxCounter로 바꿉니다.

 

이렇게 O(N)으로 해결할 수 있었습니다.

 

알게된 것

지금까지 부담 없이 사용했던 max( )는 O(N)이었습니다.

지금까지 왜 이렇게 편하게만 생각했는지 이해가 안 될 정도네요.

만약 이 문제에서 max( )로 최대값을 구한다면 O(N^2)이 되는 것입니다.

그래서 아래 코드에서 보듯이 increase 연산을 할 때 max 값을 구해줬습니다.

이런 사소한 곳에서도 많은 최적화가 가능하구나... 라는 것을 알게 되었습니다.

 

추가로 Array(repeating:, count:)는 O(배열 길이)이라는 것! ㅎㅎ..

아래 코드의 주석처리한 부분은 이 부분을 생각하지 못해 O(N+M)으로 실패한 것입니다.

 

코딜리티... 시작하길 아주 잘한 것 같아요!

 

전체 코드

import Foundation

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var array: [Int] = Array(repeating: 0, count: N)
    var maxValue = 0, maxCounter = 0
    for counter in A {
        if counter == N+1 {
            maxCounter = maxValue //맨 뒤에 후처리 한다
        } else {
            if array[counter-1] < maxCounter {
                array[counter-1] = maxCounter
            }
            array[counter-1] += 1
            maxValue = max(maxValue, array[counter-1]) //array.max()는 O(N)
        }
    }

    for (i, num) in array.enumerated() {
        if num < maxCounter {
            array[i] = maxCounter
        }
    }

    return array
}

//O(N+M)
//public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
//    var array: [Int] = Array(repeating: 0, count: N)
//    var maxValue = 0
//    for counter in A {
//        if counter == N+1 {
//            array = Array(repeating: maxValue, count: N)
//        } else {
//            array[counter-1] += 1
//            maxValue = max(maxValue, array[counter-1]) //array.max()는 O(N)
//        }
//    }
//
//    return array
//}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.