[백준] 17087번(숨바꼭질 6)

백준 17087번

처음 제출한 코드(시간초과)

import sys
input = sys.stdin.readline

N, S = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))
arr = list(set(arr))
result = []

for i in arr:
  result.append(max(S,i)-min(S,i))

gcd = 0

for j in range(min(result), 1, -1):
  for k in arr:
    if (k-S)%j != 0:
      break
  else:
    gcd = j
    break

if gcd==0:
  gcd = 1
  
print(gcd)

◼ 이중 for문을 활용해서 나와 동생 N명 사이 거리의 집합들의 최대공약수 찾기

• 나와 동생 N명 사이의 거리의 집합을 생성
• 집합에서 가장 작은 수(가장 가까운 거리)부터 1씩 줄여가며 집합 내의 모든 원소에 대해 약수가 될 수 있는지 검사한다.
  ⇒ T(n) = cn
  ⇒ c의 값에 따라 최악의 경우 O(n**2)보다 오래 걸릴수도...
  .

◼ 시간초과
.
◼ 최대공약수를 구하는 부분의 실행시간을 줄여야 함

최종 제출 코드

def get_gcd(a,b):
  while b:
    mod = b
    b = a%b
    a = mod
  return a
  
N, S = map(int, input().split())
arr = list(map(int, input().split()))
result = []

for i in arr:
  result.append(abs(S-i))

result = list(set(result))

gcd = min(result)
for j in range(len(result)):
  gcd = get_gcd(result[j], gcd)

print(gcd)

◼ 최대공약수를 구하는 부분을 수정

◼ 나와 동생들 사이의 거리를 원소로 하는 집합을 돌면서 각각의 원소와 최소 거리의 최대공약수를 구하며 gcd를 업데이트 해준다
⇒ gcd는 최대공약수로 업데이트 되기 때문에 집합 내의 어떤 원소보다도 클 수 없다
⇒ T(n) = c*n
⇒ O(n) = n*log2n

참고한 코드