수 나누기 게임 ( 27172 번 )

27172번: 수 나누기 게임

 

🧠 알고리즘

입력 리스트 n_list의 값들을 키로 하는 딕셔너리 n_dict 생성
각 수 에 대해, i의 배수 들을 탐색
최종적으로 n_dict 값 들을 리스트로 변환해 출력

 

🧾 코드

import sys

def _main(n, n_list):
    n_dict, max_value = {}, 0
    for i in n_list:
        n_dict[i] = 0
        max_value = max(max_value, i)

    for i in n_list:
        for j in range(i*2, max_value + 1, i):
            if j in n_dict:
                n_dict[i] += 1
                n_dict[j] -= 1

    answer = list(n_dict.values())

    return ' '.join(map(str, answer))


n = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, n_list))

 

⏱️ 시간 복잡도

for i in n_list : i를 순회 ( 선형 시간 복잡도 )
	for j in range(i*2, max_value + 1, i) : 배수 탐색 ( 선형 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 O(n ** 2)