[python] codility: MaxCounters

app.codility.com/programmers/lessons/4-counting_elements/

4. Counting Elements lesson - Learn to Code - Codility

 

Lesson 4 Counting Elements 의 2번째 문제다.

 

주제는 카운팅인 것 같다.

코딜리티의 특징은, 테스트 케이스는 적게 내주고 실제 채점 케이스에서 좌절감을 느끼게 해주는 것 같다.

 

그래서 더 큰 도움이 되는듯. 라인 코테를 봐보니 내가 풀어도 이걸 풀었다 할 수 없겠다라는 느낌이 드는 문제들이 있다.

 

알고리즘에서 제일 중요한 건, 테스트 케이스 외에 어떤 히든케이스 들이 나를 괴롭힐 것인가 예상하고 대책을 코드에 세워놓는 것이다.

 

그리고 또 중요한 것은 시간 복잡도다. 

wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

이렇게, 내가 무슨 함수들을 사용할지에 따라 시간복잡도가 천차만별일 수 있기에 고려해서 만들지 않으면 codility 테스트들은 100% 정답을 맞기가 힘들 것이다.

고민을 많이 하는 연습을 하니 100%도 맞네

 

그냥 테스트 케이스 통과했다고 바로 submit 하지 말아야 한다. 그게 codility 다. 그리고 네이버와 라인은 이런 식으로, 히든 케이스들이 존재하기 때문에 이 연습은 더 해야 할듯.

 

(정답코드)

def solution(N, A):
    # write your code in Python 3.6
    li = {i:0 for i in range(1,N+1)}
    max_sum = 0
    max_num = 0
    for key in A:
        if key == N+1:
            max_sum += max_num
            li.clear()
            max_num = 0
        else:
            if li.get(key) is None:
                li[key] = 1
            else:
                li[key] += 1
                
            max_num = max(max_num,li[key])
    
    answer = [max_sum] * N
    #li = sorted(li)
    for key,val in li.items():
        answer[key-1] += val 
    
    return answer

문제의 규칙은 이렇다.

 

1. 1~N 까지의 index 를 가진 카운터를 생성한다.

2. A list 의 각 요소는 숫자 M 이 적혀있는데 그 M을 index로 하는 카운터를 1 증가시킨다.

3. 만약 M = N+1 이라면 그 것은 모든 카운터의 카운팅 숫자를 카운터 중 가장 큰 수 (max_num) 으로 바꾸는 것이다.

4. 최종 카운터들의 카운팅 넘버를 리스트로 저장한다.

 

 

(2번코드)

for m in A:
	# 각 명령에 대해
    if m == N+1:
    	max_val = max(counters)
    	for i in range(1,N+1):
        #만약 N+1 이면 모든 카운터의 값을 설정한다.
        	counters[i] = max_val
    else:
    	counters[m] += 1
        max_val = max(max_val,counters[m])
    

이 문제를 만약 이런식으로 2개의 for문을 중첩시키는 형태로 하면 아마 효율성 문제에서 오답이 나오지 않을까 싶다.

(해보진 않았는데... ㅎ)

오답이 나오진 않더라도 적어도 위 1번 코드는 이 코드보다 시간복잡도 상으로 훨씬 유리하다.

 

아래 코드는 O(N*N) 의 시간복잡도가 가능하지만 1번 코드는 O(N+N) 이기 때문이다.

만약 counter 가 정의된대로 최대 10만개라면 위 코드는 100만개의 연산이 시도될 수 있고  1번코드는 20만개의 연산이 발생할 수 있다. (물론 대략적으로)