[백준] 27172 수 나누기 게임 python 풀이

문제

• 난이도: 골드5
• 알고리즘 분류: 수학, 브루트포스 알고리즘, 정수론, 소수 판정, 에라토스테네스의 체
• 요약: 서로 다른 수가 적힌 카드가 있고 수 나누기 게임을 모두 진행했을 때, 각 플레이어의 점수를 출력하기

풀이

모든 수에 대해 두개씩 비교를 진행하면 시간복잡도가 O(N^2)이다. 입력 크기가 최대 100,000개이기 때문에 시간 초과가 발생한다. 모든 숫자 쌍을 직접 비교하는 대신, 효율적으로 문제를 해결하기 위해 에라토스테네스의 체 알고리즘의 개념을 응용하여 해결할 수 있다.

나머지가 0이라는 뜻은 한쪽이 다른 쪽의 배수라는 뜻이다. 각 플레이어가 가진 수의 배수 관계만 비교해가며 빠르게 확인한다. 비교 대상이 줄어 모든 수를 확인하지 않아도 되고, 에라토스테네스의 체와 유사한 시간복잡도를 보인다. 이 과정에서 cards_with_idx 딕셔너리를 만들어 특정 수의 카드에 대한 인덱스를 빠르게 찾을 수 있도록 한다.

코드

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

cards_with_idx = {card: idx for idx, card in enumerate(cards)}
max_card = max(cards)

res = [0] * n

for i in range(n):
    cur_card = cards[i]
    for j in range(cur_card*2, max_card+1, cur_card): # j는 cur_card의 배수
        if j in cards_with_idx:
            idx = cards_with_idx[j]
            res[i] += 1
            res[idx] -= 1

for i in res:
    print(i, end=' ')