순회를 최소화한 알고리즘

아래 문제는 코딜리티에서 제공하는 MaxCounters의 문제입니다🧑🏻‍💻

 

문제 제시

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. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0) (0, 0, 1, 1, 0) (0, 0, 1, 2, 0) (2, 2, 2, 2, 2) (3, 2, 2, 2, 2) (3, 2, 2, 3, 2) (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

public func solution(_ N : Int, _ A : inout [Int]) -> [Int]

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

 

문제 해결

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var resultArr = [Int](repeating: 0, count: N)
    var maxValue = 0
    var maxCount = 0
    
    for data in A {
        let index = data - 1
        
        if data < N + 1 {
            if resultArr[index] <= maxValue {
                resultArr[index] = maxValue
            }
            resultArr[index] += 1
            
            if resultArr[index] > maxCount {
                maxCount = resultArr[index]
            }
        } else {
            maxValue = maxCount
        }
    }
    
    return resultArr.map { $0 < maxValue ? maxValue : $0 }
}

/*
  A[0] = 3 >> mv = 0, mc = 1
  A[1] = 4 >> mv = 0, mc = 1
  A[2] = 4 >> mv = 1, mc = 2
  A[3] = 6 >> mv = 2, mc = 2
  A[4] = 1 >> mv = 2, mc = 3
  A[5] = 4 >> mv = 2, mc = 4
  A[6] = 4 >> mv = 2, mc = 5
*/

 

사용된 개념

 - 배열 순회

 - 고차함수(map)

 - 삼항연산자

 - 반복 / 조건문

 

문제 뒷담화

해당 문제는 배열의 순회를 얼마나 줄이면서 시간 복잡도를 낮출 수 있는지에 대한 문제였다.

우선 간단히 문제를 해석하면 A배열안에 데이터 - 1의 정수값이 증가시키고자 하는 배열의 인덱스 값이 된다.

해당 값이 들어오면 해당 인덱스 위치의 값을 1만큼 증가시키고 만약 데이터값이 배열의 길이 + 1의 값이 들어온다면

그 시점에 해당하는 배열의 가장 큰 수의 값만큼 모든 배열의 데이터를 맞춰준다.

이렇게 이해하고 접근을 시작한다.

가장 변수는 모든 값들을 변경시키는 값이 불릴때 어떻게 처리할지에 대한것인데 그때마다 이중 for문을 쓰거나 반복을 돌려주게되면

시간 복잡도는 O(N * M)을 가지게 됨으로 효율성이 떨어진다.

지나간 반복들을 뒤로하고 전체 변경되는 값의 조건이 불렸을때의 시점의 최대값을 저장해두었다가 마지막에 반환할때

map을 사용하고 삼항연산자를 사용하여 조건을 비교해주어 놓친 데이터의 값 변경을 해준다면 시간 복잡도를 낮출 수 있다.

maxValue는 현재 시점에서의 최대값이며 maxCount는 배열에서 매 순간 시점에서 가장 큰 값을 담은 변수로 해당 두 변수의 흐름을

위 코드의 주석으로 나타내놓았다.

for문을 처음에 돌면서 전체 값을 변경하지 않는 if문을 설정하고 그 안에서 maxValue와 비교하는데 이말은 해당 조건 비교 전 이전

시점에서 전체 값 변경이 이뤄졌다면 maxValue가 다른값을 가지고 있을테니 맞춰주고 값을 1만큼 올려준다.

그 다음 if문은 현재 변경해준 값이 전체 배열에서 제일 큰 수 인지 판단하고 maxCount를 변경해주는것이다.

마지막으로 else문은 전체 값 변경의 조건이 들어오면 maxValue를 maxCount로 바꿔줘 추후 반환 및 다음 조건 비교 시 사용된다.

 

 

[참고자료]

https://app.codility.com/c/run/trainingSGNNF6-JTR/

Codility