[백준/BOJ] 27172번 - 수 나누기 게임 (Python)

· 문제링크

https://www.acmicpc.net/problem/27172

27172번: 수 나누기 게임

· 핵심 : 약수 + 시간복잡도 

→ 문제 요약 : 내가 다른 수를 나눠서 나머지가 0이면 +1 득점, 나뉘어진 수를 가진 상대방은 -1 감점

1. 시간복잡도 계산

→ 바로 떠오르는 풀이는 이중 for문 써서 전부 확인하는 방법 

→ N = 100,000이므로 이중for문 사용하면 반드시 시간초과 발생 

2. 약수 구하기 

→ 제곱근까지만 확인하기 : 시간복잡도 O(N^(1/2))

3. +1 과 -1 의 의미 생각하기

→ +1 의 의미: 약수로 나를 가지고 있다! 각 숫자가 갖는 약수에서 내가 몇 번 등장했는지 체크하기

    Ex) 3 4 12 15 16 이 입력으로 들어올 때,약수에 3번이 총 몇 번 등장해? 12와 15에서 2번 등장! 따라서 3은 +1 * 2 획득 

→ -1의 의미: 특정 값의 약수인 내가 「입력으로 들어온 숫자들」 에 존재하면 어떻게 될까? 내가 나뉘어지므로 -1 감점 당한다.

    Ex) 3 4 12 15 16 이 입력으로 들어올 때, 12의 약수를 생각해보자. 1 2 3 4 6으로 그런데 약수 중 3과 4는 입력으로 들어온 숫자에 존재함. 그렇다는건 내가 3과 4로 나뉘어져서 -1 * 2 해서 2점을 감점 당하는 상황이라고 생각할 수 있음.

---

· 코드(Python)

# https://www.acmicpc.net/problem/27172
# 시간복잡도 : 이중포문 - 100 000 * 100 000 = 10^10 > 시간초과
# 내가 얻은 카드 숫자의 약수가 다른 사람에게 있는지 없는지 판단하는게 포인트!
from collections import Counter

def get_divisors(num):
    divisors = set()
    sqrt_num = int(num ** 0.5) + 1
    for i in range(1, sqrt_num):
        if num % i == 0:
            divisors.add(i)
            if i != 1 and i != num // i:
                divisors.add(num // i)
    return divisors

n = int(input())
nums = list(map(int, input().split()))

dic = {}
for num in nums:
    dic[num] = get_divisors(num)
    
scores = [0] * n

divisor_counter = Counter()
for key, value in dic.items():
    for div in value:
        if div in dic:
            divisor_counter[div] += 1
            divisor_counter[key] -= 1

for idx, num in enumerate(nums):
    scores[idx] = divisor_counter[num]

print(*scores)