[Swift 알고리즘] Codility lesson4 - MaxCounters

안녕하세요 코코종입니다

오늘 푼(사실은 어제 풀었는데 77퍼만 맞아서 답을 봐버린) 문제는 MaxCounters입니다.

 

A에서 N보다 이하의 수가 등장하면 배열에서 해당 숫자의(index-1) 값을 1만큼 올려주고

N+1이 등장하면 배열의 가장 큰 값으로 모든 배열을 바꿔주는 동작을 할 때 결과 배열을 답으로 제출하는 것이 문제입니다.

 

처음에 든 생각은 너무 쉬워서 거의 구현문제라고 생각했는데 역시나... 틀렸습니당^^

문제 그대로 작업했더니 큰수에서 시간 복잡도에서 걸리더라구요...

 

그래서 수정을 쪼금 한 버전은 N+1에서 모든 배열의 값을 다 바꿔주는게 아니라 그냥 새로운 배열( Array(repeating: maxValue, count: N))으로 덮어써버리는 것이었는데요... Array(repeating: maxValue, count: N) 도 사실 O(N)이라고 하더라구여 ^^

 

그래서 쬐금 더 수정한게 dictionary로 저장하고 쓰는거였는데,,, 네.. 또 틀렸습니다..ㅜㅜ

그래서 결국 검색을 해서 아이디어를 참고하게 되었습니다.

(아니 근데 코딜리티는 왜 이전에 제출한 답을 저장을 안해주는거죠? 킹받네....)

 

---

아이디어는 다음과 같습니다.

1. 배열 전체를 매번 수정하는건 상당히 cost가 많이 드니 마지막에 해준다

2. 평준화 할 숫자(maxCount)를 따로 저장해서 해당 인덱스에 접근 할때만 배열의 값을 수정해주고, 진짜 배열의 가장 큰 숫자(maxValue)도 갱신을 해준다.

3. N+1을 만났을 때 maxCount = maxValue로 갱신해준다(maxValue가 결국 다음에 평준화 될 숫자인거죠)

4. 배열을 돌면서 maxCount보다 작은건 maxCount로 평준화해준다.

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var list: [Int] = Array(repeating: 0, count: N)
    var maxCount: Int = 0 // N+1 일때 평준화 할 숫자
    var maxValue: Int = 0 // 진짜 최고 숫자
    for a in A {
        if a == N+1 { 
            maxCount = maxValue
        } else {
            if list[a-1] < maxCount {
                list[a-1] = maxCount
            }
            list[a-1] += 1 
            if list[a-1] > maxValue {
                maxValue = list[a-1]
            }
        }
    }
  
    for i in 0...N-1 {
        if list[i] < maxCount {
            list[i] = maxCount
        }
    }

    return list
}

아으... 쉬운 문제인줄 알았는데 생각보다 어렵더라구요... 오늘도 출퇴근에 이 문제만 생각했네요..

대체 무슨 의도를 가지고 만든걸까.. 이러면서요 ㅋㅋㅋ 옛날에 어디서 '코딜리티는 컴퓨터적 사고를 늘려준다' 라고 한 글을 봤는데 쪼금 이해할지도??