본문 바로가기
개발/알고리즘 문제

[Codility] MaxCounters

by 유다110 2017. 11. 13.
반응형

0. 문제

리스트 A와 N개의 카운터가 주어진다.

카운터는 처음에 모두 0으로 세팅되며, N이 5이면 카운터는 (0, 0, 0, 0, 0) 이다.


이때, 

만약 1 <= A[K] <= N 이라면, 카운터에서 K번째 카운터를 increase(K) 한다.(increase(K)는 K번째 카운터를 +1 한다는 것)

만약 A[K] = N+1 이라면, max counter를 한다.(max counter는 모든 카운터를 카운터 최대값으로 세팅하는 것)


그러니까 이를 따르면,

A = [3, 4, 4, 6, 1, 4, 4]

N = 5

일 경우에 


A[0] = 3   (0, 0, 1, 0, 0)

A[1] = 4   (0, 0, 1, 1, 0)

A[2] = 4   (0, 0, 1, 2, 0)

A[3] = 6   (2, 2, 2, 2, 2)

A[4] = 1   (3, 2, 2, 2, 2)

A[5] = 4   (3, 2, 2, 3, 2)

A[6] = 4   (3, 2, 2, 4, 2)


이렇게 된다.


파라미터로 리스트 A와 양의 정수 N이 주어질 경우 마지막 카운터를 리턴하라.



1. 답변

사실 문제를 보고 이해했다기보다는 예시를 보고 이해했다.

내가 짠 코드는 이렇다.

def solution(N, A):
    c_list = [0]*N
    max_c = 0
    for val in A:
        if 1 <= val <= N:
            c_list[val - 1] += 1
            curr_c = c_list[val - 1]
            if curr_c > max_c:
                max_c = curr_c
        elif val == N + 1:
            c_list = [max_c]*N
    return c_list


처음에 내맘대로 짰더니 time complexity가 낮게 나와서 겨우 고친 게 60%...


흑 지금은 이 이상으로 오르지 않는다.

다른 사람들은 어떻게 짰는지 뒤져봐야겠어.

반응형

'개발 > 알고리즘 문제' 카테고리의 다른 글

1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번?  (2) 2018.01.16
[Codility] CountDiv  (4) 2017.11.14
[Codility] MissingInteger  (4) 2017.11.12
[Codility] FrogRiverOne  (4) 2017.11.10
[Codility] PermCheck  (4) 2017.11.09

댓글