def solve():
check = [0]*(M+1)
for i in range(N):
if nums[i]*nums[i]>M:
break
for j in range(i,N):
if (n:=nums[i]*nums[j])>M:
break
check[n] = 1
print(check.index(0))
input()
nums = sorted({*map(int,input().split())})
N = len(nums); M = 2*10**6+3
solve()
브루트 포스로 해결하였다.
일단 풀이를 설명하면,
1. 입력받은 숫자를 중복을 제거하고 정렬한다. (같은 인덱스를 뽑을 수 있어 중복숫자가 필요없다)
2. 2000003 크기의 배열을 만들고, 2중 for문을 돌면서 만들 수 있으면 check한다.
3. 체크되지 않은 숫자 중 가장 작은 숫자를 출력한다.
N이 최대 200만이기 때문에 브루트 포스로 해결할 수 없다고 생각했다. (시간복잡도가 O(N^2)이므로)
하지만 숫자들의 최댓값도 200만이기 때문에 200만이 넘으면 계산하지 않을 수 있어 실제 시간복잡도는 더 작게된다. (에라토스테네스의 체 시간복잡도가 O(N^2)이 아닌것과 비슷하다)
이때, 1에서 꼭 중복을 제거해주어야 하는것이, 중복을 제거하지 않으면 예를들어 1이 200만개가 입력되면 시간복잡도가 O(N^2)이 될 수 있다.
2에서 2000003 크기의 배열을 만드는 이유는 200만보다 큰 소수는 절대 만들 수 없기 때문이다. 200만보다 큰 가장 작은 소수가 2000003이다.
오늘의 교훈) 시간복잡도를 정확히 판단하자