[백준 23820번] MEX (Python3)

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이다.

 

 

오늘의 교훈) 시간복잡도를 정확히 판단하자