[Codility][Python] MaxCounters

문제

크기 N의 0으로 초기화된 배열 counter가 존재한다고 하자.
배열 A는 연속된 operation이다.

operation은 아래와 같은 2가지 종류가 존재한다.

• increase(X) − counter X의 값을 1 증가시킨다.
• max counter − 모든 counter의 값을 counter들 중의 최대값으로 갱신한다.

이 operation은 다음과 같은 조건으로 수행된다.

A[K] = X 일 때,

• 1 $\leq$ X $\leq$ N 라면,
  operation K는 increase(X)이다.
• X $=$ N+1 라면,
  operation K는 max counter이다.

입출력 예시는 다음과 같다

입력
N : 5
A : [3, 4, 4, 6, 1, 4, 4]

과정

i	A[i]	counter
0	3	(0, 0, 1, 0, 0)
1	4	(0, 0, 1, 1, 0)
2	4	(0, 0, 1, 2, 0)
3	6	(2, 2, 2, 2, 2)
4	1	(3, 2, 2, 2, 2)
5	4	(3, 2, 2, 3, 2)
6	4	(3, 2, 2, 4, 2)

반환
(3, 2, 2, 4, 2)

제한 :
1 $\leq$ N, M $\leq$ 100,000
1 $\leq$ 배열 A의 원소 $\leq$ N + 1
(M : 배열 A의 길이)

---

접근

내용 자체는 굉장히 간단한 문제이나,
문제의 시간 제한으로 더 시간 효율적인 접근 방법을 찾는것이 관건인 문제이다.

간단하게

생각해 볼 때,
counter라는 길이 N의 배열을 선언한 뒤,
배열 A를 순회하며 조건에 맞는 연산을 해주면 그만이다.
이러한 생각을 바탕으로 나온 코드는 아래와 같다.

def solution(N, A):
	counter = [0] * N
    max_value = 0
    for i in range(len(A)):
    	if 1 <= A[i] <= N:
        	counter[A[i]-1] += 1
            max_value = max(max_value, counter[A[i]-1])
        else:
        	for j in range(len(counter)):
            	counter[j] = max_value
	return counter

정답은 잘 출력되지만, N값이 커지는 케이스에서는 시간초과를 면하지 못한다.
여기서 시간 복잡도를 더 줄여주기 위해서는 어떻게 해야할까?

1. 현재 counter의 최소값도 같이 갱신한다.

지금은 max_value만 유지하고 있지만,
max counter operation이 들어오는 시점에 counter의 최소값을 알고 있다면,
최소값과 최대값이 같은 경우 (이미 모든 counter가 최대값인 경우)에는 counter를 순회하는 반복문을 돌지 않아도 되기 때문에 불필요한 연산을 하지 않을 수 있다고 생각했다.

그런데 counter의 최소값은 어떻게 갱신할까?
max_value를 갱신한 것 처럼
min_value = min(min_value, counter[A[i]-1])
이렇게 해주면 될까?
아니다. 이렇게 갱신한 값은 최초의 최소값만 계속 유지될 뿐이다.
그렇다면 어떻게 counter의 현재 최소값을 유지할 수 있을까?

2. 최소값을 갱신하는 방법

현재 배열의 최소값을 알기 위해서는,
값을 index로 하고,
그 값을 가지고 있는 counter의 개수를 알고있는 배열이 필요하다고 생각했다.

무슨 말이냐 하면,
만약 counter가 다음과 같은 상태라고 하자
(0, 1, 2, 2, 1)

그렇다면, 우리가 만들려는 새로운 배열(B라고 하자)은 다음과 같은 상태일 것이다.

i	B[i]
0	1
1	2
2	2
3	0
...	...

우리는 counter에 operation을 적용함에 따라,
그 값을 가진 counter의 개수를 배열 B를 통해 처리해줄 수 있다.

만약 현재까지의 최소값이 min_value인데,
increase(X) operation을 통해 B[min_value] 가 0이 된다면,
min_value = min_value+1 이 될 것이고,
max counter operation을 실행한다면
min_value = max_value 가 될 것이다.

이때 배열 B의 길이는 operation으로 나올 수 있는 최대값이기 때문에,
배열 A의 길이 + 1 로 초기화 해야한다.

이런 생각을 바탕으로 아래와 같은 코드가 나왔다.

def solution(N, A):
	counter = [0] * N
	B = [0] * (len(A) + 1)
	B[0] = N
	max_value = 0
	min_value = 0
	for i in range(len(A)):
		if 1 <= A[i] <= N:
			B[counter[A[i]-1]] -= 1
			if B[min_value] == 0: min_value += 1
			counter[A[i]-1] += 1
			B[counter[A[i]-1]] += 1
			max_value = max(max_value, counter[A[i]-1])
		else:
			if min_value < max_value:
				for j in range(len(counter)):
					counter[j] = max_value
			min_value = max_value
			B[min_value] = N
	return counter

그런데 현재 counter의 최소값을 유지시킬 수 있다면,
counter를 순회하는 반복문을
max counter operation이 있을 때 마다 실행 할 필요가 있을까?

counter의 값은 increase(X) operation이 있을 때 $O(1)$로 증가한다.
그렇다면, 이 최소값을 이용해서
max counter operation을 lazy하게 적용 해 줄 수 있지 않을까?

3. 어떻게?

increase(X) operation이 있을 때
counter[A[i]-1] < min_value 가 True 라면,
이 때 비로소 counter[A[i]-1] 의 값을 min_value로 갱신해주면 된다.
또한, max counter 이후 마지막 operation까지 increase(X) 가 일어나지 않은 counter가 있을 수 있으므로
마지막에 counter를 순회하며 min_value보다 작은 값을 가지는 counter의 값을 min_value로 갱신해주어야 한다.

max counter가 실행된다고 해서 B의 max_value보다 작은 인덱스의 값들을 0으로 초기화 시켜줄 필요는 없는데,
이는 A에 담긴 operation들이 전부 counter를 증가시키는 연산이기 때문이다.

코드

def solution(N, A):
	counter = [0] * N
	B = [0] * (len(A) + 1)
	B[0] = N
	max_value = 0
	min_value = 0
	
	for i in range(len(A)):
		if 1 <= A[i] <= N:
			if counter[A[i]-1] < min_value:
				counter[A[i]-1] = min_value
			B[counter[A[i]-1]] -= 1
			if B[min_value] == 0: min_value += 1
			counter[A[i]-1] += 1
			B[counter[A[i]-1]] += 1
			max_value = max(max_value, counter[A[i]-1])
		else:
			min_value = max_value
			B[min_value] = N

	for i in range(len(counter)):
		if counter[i] < min_value:
			counter[i] = min_value
	return counter