[Codility] (Swift) MaxCounters

네이버 코테를 보기 위해서 Codility를 처음으로 이용해보았다. codility에서 코드를 작성하는 부분은 programmers와 크게 다를바가 없었고, 더 좋았던 점은, 시간복잡도에 대한 검증을 더 자세하게 해준다는 것이었다!

 

일단 '기초'부터 다시 잡자는 마인드로 공부중인 요즘, 일단 Lesson에 있는 Medium 문제들만 먼저 골라서 풀었다.

 

🟠 문제 

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

Codility

문제는 전부... 영어다...🥹

 

🟠 오답으로 알아가는 내 코드의 문제점

처음 오답 코드는 다음과 같다

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

    for idx in 0..<A.count {
        if A[idx] == N+1 {
            let max = answer.max()!
            answer = Array(repeating: max, count: N)
        } else {
            answer[A[idx]-1] += 1
        }
        print(answer)
    }

    return answer
}


print(solution(N, &A))

이렇게 하니까, 정답은 맞췄지만, 효율성테스트(시간복잡도)에서 전부 fail을 받았다. 왜일까?

이 문제에서는 두가지의 연산이 수행된다. N+1과 같지 않다면, +1 연산을 수행하고, 같다면 배열 전체를 Max로 바꿔주는 연산을 수행해야한다. 여기서 핵심은, 배열 전체를 바꿔주는 부분에서 발생했다.

나는 역시나, answer배열을 새롭게 max값으로 갱신하는 방식으로 진행했다. 이 과정에서, 배열이 아주 커질 경우, 시간복잡도가 굉장히 커질것으로 예상됐다. 음 예를들어 현재 내가 짠 코드의 시간복잡도는 O(N+M)인데, 만약 배열의 길이가 10000일경우, for문 내에서 최대 10000번의 배열갱신이 이루어진다. fo문을 줄일 수는 없고, 이 연산을 최소화할 순 없을까?

(인터넷의 도움을 조금 받았다ㅜㅜ 아직 너무 멍청,,해,, 흑) max연산을 최소화해야한다. 그렇다면, max값을 다른곳에 저장해두고, 필요할때만 max값을 갱신해주면 어떨까! 이 방식으로 코드를 짜봐야한다. 

 

🟠 정답코드

아래와 같은 형식으로 코드를 짰다. 코드를 조금 풀어보자면 아래와 같다.

1. currentMax: N+1일 때, 바꿔줄 현재 가장 큰 max 값이다.
2. nextMax: +1했을때 만약 해당 값이 가장 max값이라면, nextMax에 잠깐 넣어준다.
3. for문
   1. N+1이 아니라면,  +1 연산을 수행한다.
   2. 현재 값이 currentMax값보다 작다면, max값이 아니니까 max값으로 바꿔준다.
   3. 그리고 +1 해준다.
   4. 만약, 해당 값이 nextMax보다작으면, currentMax값이 될 명분이 충분히 되니까, next에 잠깐 넣어준다.
   5. N+1 이라면
   6. currentMax에 nextMax를 넣어주면서, max값을 갱신해준다.
4. 마지막에 max값으로 변하지 않은 것들을 currentMax와 비교해서 바꿔준다.

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    var answer = Array(repeating: 0, count: N)
    var currentMax = 0
    var nextMax = 0

    for a in A {
        // N+1 이 아니라면
        if a != N+1 {
            // +1 연산해줘야해
            // 그전에 currentmax값이 존재한다면, 그 값으로 바꿔주고
            // (max값보다 작을경우, 바꿔줘, 만약 크면? 이미 +1씩 더하고 있다는 뜻
            if answer[a-1] <= currentMax {
                answer[a-1] = currentMax
            }

            answer[a-1] += 1

            // 만약 지금 +1 해준 값이 max가 될 가능성이 있다면
            // nextmax에 넣어줘,,, (다음에 바궈줄때 사용)
            if answer[a-1] > nextMax {
                nextMax = answer[a-1]
            }
        } else {
            currentMax = nextMax
        }
    }

    // 최댓값으로 바꿔지지 않은 것들 바꿔주기
    for idx in 0..<answer.count {
        if answer[idx] < currentMax {
            answer[idx] = currentMax
        }
    }

    return answer
}
print(solution(N, &A))