[codility][python] max counter

codility max counter

https://app.codility.com/demo/results/trainingUBUCBJ-RVE/

def solution(N, A):
  res = [0] * N
  max_counter = 0

  for a in A:
    if a <= N:  # N카운터 존재
      res[a-1] +=1  # 카운터 올림
      if max_counter < res[a-1]: # max_counter 보다 크면 현재 카운터를 tmp_max로 변경
        max_counter = res[a-1] 
    else: # max counter 실행
      for i in enumerate(res):  # 전부 max_counter로 덮어씌운다.
        res[i] = max_counter
  return res

빅오노테이션이 O(MxN) 인 관계로 이중포문에서 하나를 없애야 한다.

# N 카운터가 있음. 0으로 세팅
# max counter : 모든 카운터들이 아무 카운터의 최대 값으로 세팅됨.

# A[K] = X 이면, K오퍼레이션은 X를 증가시킨다.
# -> 값이 X면 X를 증가시킴 (X범위 1<=X<=N)
# A[K] = N + 1 이면 K는 max counter  (??? K가 N보다 크면 max??)
# 아아아 max counter라는 걸 실행함!!!

def solution(N, A):
  res = [0] * N
  max_counter = 0
  tmp_max = 0
  for a in A:
    if a <= N:  # N카운터 존재
      if max_counter > res[a-1]:  # 1 max_counter가 더 크면 max_counter가 갱신된 것
        res[a-1] = max_counter  # 2 max_counter 값으로 변경해준다.
      res[a-1] +=1  # 3 그리고 그 다음에 카운터 시킨다
      if tmp_max < res[a-1]:  # 4 tmp_max보다 크면 현재 카운터를 tmp_max로 변경
        tmp_max = res[a-1]

    else:  # max_counter 에 현재 tmp_max를 넣는다. (max_counter는 그때그때 실행할 것이다.)
      max_counter = tmp_max

  # 아직 max_counter가 변경 된 이후에 counter가 변경된 이력이 없으면 max_counter로 덮어씌워준다.
  # 물론 max_counter보다 작은 경우.
  for idx, _ in enumerate(res):  
    if (res[idx] < max_counter):
      res[idx] = max_counter

  return res

a = [3,4,4,6,1,4,4]
N = 5

print(solution(5, a))