(코딜리티) Lesson 11. [Sieve of Eratosthenes] : CountNonDivisible - python

문제 : app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_non_divisible/

CountNonDivisible coding task - Learn to Code - Codility

문제 내용

N개의 배열 A가 주어질 때, 각 요소마다 배열 A에 있는 원소들로 나누어지지 않는 원소의 갯수를 구하시오.

 

예를 들어,

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

A[0] = 3, 나눠지지 않는 수 : 2, 6

A[1] = 1, 나눠지지 않는 수 : 3, 2, 3, 6

A[2] = 2, 나눠지지 않는 수 : 3, 3, 6

A[3] = 3, 나눠지지 않는 수 : 2, 6

A[4] = 6, 나눠지지 않는 수가 없음

따라서, [2, 4, 3, 2, 0]을 return하면 된다.

제한 사항

• N은 1~50,000
• A의 각 요소는 1~2*N

코드

def solution(A):
    
    N = len(A)
    #배열 A의 원소갯수를 담을 list, index가 원소가 됨
    element = [0]*(2*N+1)
	
    #배열 A에서 각 원소갯수를 카운트
    for a in A:
        element[a] += 1
    
    answer = [0]*N
    
    #A를 for문돌다가 똑같은 요소인 경우 저장해서 바로 사용하기 위함
    saved = [-1] * (2*N+1)
    for i in range(N):
        current = A[i]
		
        #이전에 똑같은 원소가 나온 경우
        if saved[current] != -1:
            answer[i] = saved[current]
        else :
            count = 0
			
            #현재 원소의 약수를 구하기 위하며, 만약 6인 경우 1,2,3,6이니 2까지만 for문을 돌고 3은 동시에 카운트
            for j in range(1, int(current**0.5) + 1):
                if current%j == 0:
                    count += element[j]
					
                    # current가 4인경우 j가 2인 상황을 위함. 1,2,3,6일 때 2와 3처럼 대칭인 부분이 없기때문
                    if j != current//j:
                        count += element[current//j]
			
            # 양수를 구한 후 전체 값을 빼면, 원하는 답이 나옴
            answer[i] = N - count
            # 원소를 저장했다가 중복되는 경우 똑같은 값으로 사용하기 위함
            saved[current] = answer[i]

    return answer

해설

1. 배열 A의 원소들을 index로 하여금 list를 생성하여 count를 함
2. 배열 A를 for문을 돌리면서 하나씩 약수 갯수를 구함
3. 검토 할 때는 원소의 제곱근까지 for문을 돌리며, 배열 A안에 약수가 있는지 검토하고, 대칭되는 반대편의 값(current//j)도 검토하여 count
4. 중복되는 원소가 있으면 바로 값을 꺼내기 위해 saved에 저장해서 사용