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

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

27172번: 수 나누기 게임

 

문제 해결

• 단순히 두개씩 비교를 하면 시간복잡도가 $O(N^{2})$이 나온다.
• 이러면 시간안에 통과를 못하는데 이를 보완하기 위해 에라토스테네스 체를 이용하려 한다.
• 주어진 플레이어가 가진 수들을 리스트 안에 넣고, 그 중 최대치를 maxNum 변수에 저장한다.
• 각 플레이어가 가진 수들의 배수를 확인해가며 플레이어가 가진 수들 중 있는지 확인을 해가며 점수를 수정한다.

 

CODE

import sys
from collections import deque
input = sys.stdin.readline


def solve():
    for li in range(n):
        _ , num = l[li]

        for target in range(num*2, maxNum+1, num):
            if target in answer:
                answer[num] += 1
                answer[target] -= 1
    for key, item in answer.items():
        print(item, end=" ")

if __name__ == '__main__':
    n = int(input())
    l = []
    answer = dict()
    maxNum = 0

    for i, num in enumerate([*map(int, input().strip().split())]):
        maxNum = max(maxNum, num)
        l.append((i, num))
        answer[num] = 0
    l.sort(key=lambda x : x[1])

    solve()