[백준] 27172번 수 나누기 게임 ★

💡문제접근

• 어떤 수가 등장했는지 여부를 배열에 처리한다.
• 주어진 플레이어의 카드 배열의 수 x에 대해 x의 배수 y(y > x)를 모두 확인하고 y가 주어진 플레이어의 카드 배열에 등장한 적이 있는지 확인한다.
• 위의 경우에서 등장 여부를 따지는 배열에서 배열[y]의 값이 1인 경우(=등장했다면?) y는 x로 나누어 떨어진다. 다른 플레이어의 카드가 현재 플레이어의 카드 수로 나누어 떨어지면 현재 플레이어의 승리, 다른 플레이어의 패배가 된다.

💡코드(메모리 : 140684KB, 시간 : 308ms, PyPy3로 제출)

import sys
input = sys.stdin.readline

N = int(input())
card = list(map(int, input().strip().split()))

result = [0] * 1000001   # 최종 결과
arr = [False] * 1000001      # 등장 카운트
# 어떤 수가 등장했는지 여부를 크기 1000000 배열에 처리
for x in card:
    arr[x] = True

# 주어진 배열의 수 x에 대해서
for x in card:
    # x의 배수 y > x를 모두 확인함
    for y in range(x*2, 1000001, x):
        # y가 등장한 적이 있다면?
        if arr[y]:
            # x += 1, y -= 1
            result[x] += 1
            result[y] -= 1

for x in card:
    print(result[x], end = " ")

💡소요시간 : 34m

📌Big-O notation과 시간 제한

100,000,000(1억) = 1초의 시간 제한

• N의 최대값이 10만이라고 문제에서 주어지는 경우

• 1. O(N)의 시간복잡도일 경우 -> 값 : 100,000이므로 1/1000초가 걸린다고 예상 가능
• 2. O(N^2)의 시간복잡도일 경우 -> 값 : 10,000,000,000이므로 100초가 걸린다고 예상 가능

따라서 문제의 시간 제한이 1초인 경우 O(N^2)의 시간복잡도를 가지는 알고리즘으로 문제를 해결할 수 없다는 것을 미리 알고 코드 작성에 돌입해야한다.