머리 톡톡 ( 1241 번 )

1241번: 머리 톡톡

 

---

🧠 알고리즘

• 약수 탐색 + 해싱(Dict 캐싱)

 

✔️ 동작 방식

• 모든 수를 읽어서 num_list에 저장, num_dict에 각 수의 빈도를 기록
• 약수 탐색 함수 _cr(i, num_dict)
• 각 수 i에 대해 _cr(i, num_dict) 실행
• 이미 계산한 값이면 hash_dict에서 꺼내 재사용
• 결과를 문자열 리스트로 모아 출력

---

 

🧾 코드

import sys

def _cr(i, num_dict):
    answer = 0
    for num in range(1, int(i ** (1/2)) + 1):
        if i % num == 0:
            if num in num_dict:
                answer += num_dict[num]
            if num ** 2 != i:
                if i // num in num_dict:
                    answer += num_dict[i // num]

    return answer - 1


def _main(n):
    answer = []
    num_dict = {}
    num_list = []

    for _ in range(n):
        num = int(sys.stdin.readline().rstrip())
        num_list.append(num)
        if num not in num_dict:
            num_dict[num] = 1
        else:
            num_dict[num] += 1

    hash_dict = {}
    for i in num_list:
        if i in hash_dict:
            answer.append(str(hash_dict[i]))
        else:
            tktk = _cr(i, num_dict)
            hash_dict[i] = tktk
            answer.append(str(tktk))           
    
    return '\n'.join(answer)
    
n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for i in num_list : 숫자 리스트를 순회 ( 선형 시간 복잡도 )
	tktk = _cr(i, num_dict) : 약수 확인 및 결과 리턴 함수 ( 로그 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )