문제

입출력 및 조건

접근

일단 모든 케이스를 다루는 브루트 포스는 어쩔 수 없이 해야한다. 문제 조건 자체에서 모든 플레이어가 본인을 제외한 다른 플레이어 전원과 게임을 해야하는게 조건이라 그러하다.

단순 2중 for문은 정답이 되지 않는다.

접근 1

l = [*map(int,input().split())]

'''
1. 단순 반복 -> n 100,000 이라서 N^2형태로 구현시 무조건 시간초과.

'''

n = int(input())
answer = [0]*n

for i in range(0,n-1):
    cur = l[i]
    for j in range(i+1,n):
        enemy = l[j]
        
        if enemy % cur == 0:
            answer[i] += 1
            answer[j] -= 1
            
        elif cur % enemy == 0:
            answer[i] -= 1
            answer[j] += 1
        else: pass

가장 심플한 형태지만 O(n^2) 만큼의 시간복잡도를 가지는데 n이 100,000라서 무조건 시간초과 걸린다.

접근 2

에라토스테네스의 체 응용.

에라토스테네스의 체는 소수를 판별하기 위한 알고리즘으로, 숫자 n이하의 자연수에 대해 소수를 빠르게 판별하는 알고리즘이다.

에라토스테네스의 체 자료 1
에라토스테네스의 체 자료 2
에라토스테네스의 체 자료 3 (시간복잡도 有)

나머지가 0이라는 뜻은 한쪽이 다른 쪽의 배수라는 뜻과도 같다. 따라서 1:1로 비교하는 것도 괜찮지만 숫자가 작은 것부터 골라 그수의 배수와 비교를 한다면 에라토스테네스의 체와 유사한 시간복잡도를 보일것으로 보인다. 증명은 어렵지만 에라토스테네스의 체의 시간 복잡도는 O(nlog(logn))이다.

풀이

import sys
from collections import deque

input = sys.stdin.readline

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])
   

# 입력 받은 숫자에 대해 하나하나 진행 시작.
for li in range(n):

	# 값을 num으로 받음.
    originPos, num = l[li]
    
    # 에라토스테네스의 체와 유사하게 운용
    # target은 num의 배수
    for target in range(num*2,maxNum+1, num):
    	
        # target이 만약 num에 등장한 값이라면 비교 시작.
        # target은 num의 배수이므로 무조건 target % num == 0 임.
        # 따라서 num이 무조건 이김.
        if target in answer :
            answer[num] += 1
            answer[target] -= 1
        
        
# answer를 순회하여 결과 출력
# dictionary 자료구조가 파이썬 3.6 이상에선 입력받은 순서를 기억한다고 함. 따라서 이 방식으로도 순서가 꼬이지 않음.
for key, item in answer.items():
    print(item,end=" ")

결과