[Codility/Lesson11]CountNonDivisible

| 1트

import collections
import math 

def solution(A):

    num_hash = collections.defaultdict(int)
    length = 0 

    for num in A:
        num_hash[num] += 1
        length += 1 
    
    answer = []

    for num in A:
        count = 0 
        for measure in range(1, math.floor(num ** (1/2)) + 1):
            if num % measure != 0:
                continue
            count += num_hash[measure]

            if measure * measure != num:
                count += num_hash[num // measure]
        answer.append(length - count)
            
    #print(answer)
    return answer
            

• list에 있는 수들의 갯수를 hash에 저장해놓음
• list에 있는 수 각각의 약수를 찾아서 list에 있는지 찾아본다
• list에 있는 갯수를 전체 길이에서 뺀 것이 답

결과는 여기에

이렇게 했더니 몇몇 케이스에 대해서 timeout이 걸렸다
겹치는 결과에 대해서는 저장을 해둬야 하는가보다

| 2트 ~ 3트

import collections
import math 

def solution(A):

    num_hash = collections.defaultdict(int)
    answer_hash = collections.defaultdict(lambda : -1)
    length = 0 

    for num in A:
        num_hash[num] += 1
        length += 1 

    answer = []

    for num in A:
        if answer_hash[num] != -1:
            answer.append(answer_hash[num])
            continue
        count = 0 
        for measure in range(1, math.floor(num ** (1/2)) + 1):
            if num % measure != 0:
                continue
            count += num_hash[measure]

            if measure * measure != num:
                count += num_hash[num // measure]
        
        answer_hash[num] = length - count 
        answer.append(length - count)
            
    return answer
            

• 겹치는 결과에 대해서는 저장을 하도록 했다
• 원래 defaultdict(int)를 하면 0이 default 값으로 저장이되는데, defaultdict(lambda : -1)로 하면 -1이 default로 저장이 된다(대박 최고최고🤸‍♀️)

결과는 여기에