Softeer 연습문제(2단계) - 연탄의 크기

Candidate | Softeer Assessment UI

Candidate | Softeer Assessment UI

 

나의 풀이

import sys

def _aksu(number):
    answer = [number]
    for i in range(2, int(number**(1/2)) + 1):
        if (number % i == 0):
            answer.append(i)
            if ((i ** 2) != number):
                answer.append(number // i)
    return answer

def _main(hot_size):
    ava_dict = {}
    for i in hot_size:
        now_ava = _aksu(i)
        for j in now_ava:
            if (j in ava_dict):
                ava_dict[j] += 1
            else:
                ava_dict[j] = 1
    answer = sorted(ava_dict.values(), key=lambda x:x)
    return answer[-1]

home = int(sys.stdin.readline())
hot_size = list(map(int, sys.stdin.readline().rstrip().split()))
print(_main(hot_size))

 

시간 복잡도

for i in hot_size : 각 집을 순회 ( 선형 시간 복잡도 )
    for j in now_ava : 약수를 순회하며 최종 dict 계산 ( 제곱근 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 제곱근 시간 복잡도 ( O(n * √n) )