[Codility] 11.1 CountNonDivisible

CountNonDivisible 문제 풀기

1. 크기가 N인 배열 A가 주어진다.
2. A의 원소들 중에서 A[i]의 divisor가 아닌 것들의 개수를 리스트로 반환한다.
   2.1 즉, A의 원소들 중에서A[i]의 약수를 제외한 것의 개수를 구한다(중복 허용)

어떤 수의 divisor인지 확인하는 것은 10장에서 연습했고, 딕셔너리를 이용하여 탐색을 $O(1)$으로 하였다.

cnt : A의 원소와 그 개수를 각각 (key, value)로 하는 딕셔너리. 없는 경우 0으로 초기화
nondiv : 조건을 만족하는 답이 이미 계산한 딕셔너리. 없는 경우 -1로 초기화(조건을 만족하는 답이 0일수도 있다)

def solution(A):
    cnt = dict()
    for a in A:
        cnt[a] = cnt.get(a, 0) + 1
    
    nondiv = dict()

    ret = []
    for a in A:
    	# 이미 계산한 적이 있는 경우 계산없이 바로 저장
        if nondiv.get(a, -1) != -1:
            ret.append(nondiv[a])
            continue
        total = len(A)
        m = int(a ** 0.5) + 1
        for i in range(1, m):
            if a % i == 0:
                # a가 제곱수라면 i == a//i 가 같아지는 지점이 생긴다
                # 중복으로 세지 않게 예외처리한다
                if i == a // i:
                    total -= cnt.get(i, 0)
                else:
                    total -= cnt.get(i, 0) + cnt.get(a // i, 0)
        ret.append(total)
        # 한번 계산한 답은 딕셔너리에 저장한다
        nondiv[a] = total

    return ret