문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/140107
문제 설명
- 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
- 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.
- 정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.
제한 사항
- 1 ≤ k ≤ 1,000,000
- 1 ≤ d ≤ 1,000,000
일단 문제의 제한사항을 보니 O(n^2)으로 풀면 가뿐히 시간 초과가 나올 것 같다. 그러니 O(nlogn) 이하의 시간 복잡도로 풀이하는 것이 좋을 것 같다.
사실 문제에서 요구하는 것이 그렇게 어려워 보이지는 않는다. 문제를 기하학적으로 해석해보면 원점을 중심으로하는 원의 반지름이 d일 때, 원 내부에 찍히는 (kx, ky) 좌표의 개수를 구하는 문제로 볼 수 있다.
이때, a와 b는 0을 포함한 자연수이다.
그러면 단순하게 모든 점을 다 탐색하는 방법이 제일 편하면서 오래걸리는 방법이다. (0, 0)부터 (kx, ky)까지 kx * ky번 검사하고 1씩 증가시키는 것이다. 그러면 당연히 O(n^2)의 시간 복잡도를 가지게 되고 시간 초과에 빠진다.
그러니까 우리는 조금 더 빠르게 구하는 방법이 필요하다.
x를 기준으로 1 줄씩 한번에 계산해서 한 번에 더해보자!
아래의 코드는 한 줄씩 한 번에 더해주는 방식을 적용한 방법으로 확실히 빠르다. 하지만 필자가 좀 귀찮아서 y를 1씩 빼면서 원 안에 들어가는 지 판별했다.
풀고 나서 다른 사람들의 풀이를 보니 원에 포함되는 가장 큰 수를 고른 뒤에 바로바로 더해 주는 로직을 볼 수 있었다. 이렇게 하면 O(n)으로 구하게 되는 것이고, 아래의 필자가 작성한 코드는 사실 O(n+n)이라고 볼 수 있다.
뭐 둘 다 빅오 표기법 관점에서는 O(n)이지만 이론적으로 비교 연산을 2배 수행하기 때문에 느린 것이 맞다... 개선하는 것은 여러분들이 직접 해보길 바라며 포스팅에 올리지는 않겠다.
def solution(k, d):
count = 0
y = d if d % k == 0 else d - d % k
x = 0
while x <= d:
if x**2 + y**2 <= d**2:
count += y//k + 1
x += k
else:
y -= k
return count