[Baekjoon] 17087/숨바꼭질 6/Python/파이썬/수학

💡문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

예제입력

3 3
1 7 11

예제출력

2

---

📖내가 작성한 Code

import math
import sys


def main():
    speed_input = sys.stdin.readline
    N, S = map(int, speed_input().split())
    sisters = [S] + list(map(int, speed_input().split()))
    print(math.gcd(*list(abs(sisters[i-1] - sisters[i]) for i in range(1, N+1))))


if __name__ == '__main__':
    main()

---

✍️풀이과정

그냥 최대공약수 찾기 문제 그 이상도 그 이하도 아님. 10^5 갯수라 시간 제한 1초도 든든하게 해결함. math 모듈을 오랫만에 써봄
근데 모듈 쓰지 않고 유클리드 호제법에 대한 분류가 나와있다.

유클리드 호제법

숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미

a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 b 가 0이 될때 까지 반복을
하면, 남는 a 값이 바로 최대 공약수

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

---

🧠 코드 리뷰

리스트 대신 제너레이터 표현식으로 변경하여 메모리 효율성 향상하는 것이 좋음

---

🛠️AI 개선 코드

import math
import sys
from functools import reduce


def main():
    read_input = sys.stdin.readline
    N, S = map(int, read_input().split())
    sister_positions = list(map(int, read_input().split()))
    differences = (abs(S - pos) for pos in sister_positions)
    gcd_result = reduce(math.gcd, differences)
    print(gcd_result)


if __name__ == '__main__':
    main()

---

💻결과

백준문제 보러가기

---

🖱️참고 링크

파이썬 공식 문서 - math 모듈