[알고리즘] MaxCounters, Counting,
https://codility.com/media/train/2-CountingElements.pdf
이번 문제는 잘 안풀림.
- MaxCounters Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.
맨 처음 풀이:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
'''
N개의 카운터를 받았다.
0으로 초기화됬고, 두 개의 오퍼레이션이 가능하다.
1. increase(X): X += 1
2. max counter: 모든 카운터들이 최대값으로 바뀐다. any?
비어있지 않은 배열 A: M개의 정수로 이루어졌다.
각각 연속적인 오퍼레이션을 뜻한다.
A[K] = X (X:1~N) -> K = increase(X)
A[K] = N + 1 -> K = maxCounter
'''
'''
예를 들어, N = 5 이고
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
이면
'''
# [0, 0, 0, 0, 0] 초기화에서부터
# 다음 스텝으로 변함.
# (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)
# goal: 모든 카운터들의 최종 결과를 리턴. list로.
def solution(N, A):
# N에 맞는 초기화를 세팅.
res:list[int] = [0 for x in range(N)]
# print(res)
# 모든 오퍼레이션을 차례로 수행한다.
for x in A:
if x in range(1, N):
res[x-1] += 1
else:
maxres = max(res)
res = [maxres for x in range(N)]
# print("N+1")
# print(res)
return res
이렇게 하니까 33%점수 맞음.
확실히, range(1, N+1)을 쓰는것보단 1
그리고, 복잡도가 높아져서 시간초과로 실패하는걸 개선해야함.
🔹 수정된 코드 (O(N+M))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(N, A):
res = [0] * N
current_max = 0
last_update = 0
for x in A:
if 1 current_max:
current_max = res[x-1]
else: # max counter
last_update = current_max
# 최종적으로 업데이트 안 된 값들 보정
for i in range(N):
if res[i] < last_update:
res[i] = last_update
return res
그래서 아래와 같이 고쳤는데,(고쳤는줄 알았는데)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
'''
N개의 카운터를 받았다.
0으로 초기화됬고, 두 개의 오퍼레이션이 가능하다.
1. increase(X): X += 1
2. max counter: 모든 카운터들이 최대값으로 바뀐다. any?
비어있지 않은 배열 A: M개의 정수로 이루어졌다.
각각 연속적인 오퍼레이션을 뜻한다.
A[K] = X (X:1~N) -> K = increase(X)
A[K] = N + 1 -> K = maxCounter
'''
'''
예를 들어, N = 5 이고
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
이면
'''
# [0, 0, 0, 0, 0] 초기화에서부터
# 다음 스텝으로 변함.
# (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)
# goal: 모든 카운터들의 최종 결과를 리턴. list로.
# 엣지 케이스 찾기
#
def solution(N, A):
# N에 맞는 초기화를 세팅.
res:list[int] = [0 for x in range(N)]
# print(res)
maxres:int = 0
currentMax:int = 0
# 모든 오퍼레이션을 차례로 수행한다.
for x in A:
if 1 res[x-1]:
res[x-1] = currentMax
res[x-1] += 1
if maxres < res[x-1]:
maxres = res[x-1]
else:
# 여기서 한번에 업뎃 말고, 위에서 업뎃하자.
currentMax = max(res)
# print("N+1")
# print(res)
# 최종적으로 업데이트 안된 값들 lazy update
for i in range(len(res)):
if res[i] < currentMax:
res[i] = currentMax
return res
아, 다 안고쳤구나. max는 정말 비싼 연산이구나.
currentMax = maxres 로 해서 아까 계산해놓은 maxres 그대로 쓰면 됨.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.