링크
https://school.programmers.co.kr/learn/courses/30/lessons/140107
문제
좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 한다.
- 원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍는다.
- 원점과 거리가 d를 넘는 위치에는 점을 찍지 않는다.
- 예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍는다.
정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하라.
문제 풀이
(0, 0)을 기준으로 k만큼 떨어진 좌표들의 개수를 구하는 문제이다. 이 문제는 좌표들을 실제로 찍어보게 되면 (0, 0)을 직각으로 가지는 직각이등변삼각형 형태로 좌표의 집합이 나온다.
문제 자체는 확인하려는 좌표가 피타고라스 정리에 따라 (C² = A² + B²) (0, 0)과 좌표의 거리가 d보다 작은지를 확인하면 된다.
문제를 해결하는 방법은 좌표평면에서 (0, 0)을 기준으로 우, 상 방향으로 k만큼 이동하며 점을 찍는다. 점들간의 거리가 k가 되는 방법은 여러가지가 있지만, 우방향, 상방향으로만 찍는 것이 가장 많은 경우의 수를 가진다.
따라서 우방향으로, 즉 x좌표를 k만큼 이동하고, y좌표를 0부터 k씩 증가시키며 좌표가 d 거리 안에 있는지 확인한다.
하지만 위의 방법으로 문제를 해결하는 것이 가능하지만 나오는 좌표마다 원점과 거리를 측정하기 위해서 Math.sqrt를 실행하면 시간 초과로 문제를 해결할 수 없어진다. O(n) = n²
시간 초과를 피하기 위해서 O(n) = n까지 시간복잡도를 줄여야 하는데, 그 방법은 x좌표에 대해서 나올 수 있는 최대 y값을 알아내는 것이다. 최대 y값을 알면 k로 나눈 몫에 +1을 하면 x좌표에 대해 나올 수 있는 점들의 개수를 알 수 있다. 몫에는 (x, 0)이 포함되지 않으므로 +1을 실시한다.
모든 x에 대해서 위의 과정을 반복하면 점의 개수를 구할 수 있다.
코드
// 좌표평면에서 (0, 0)을 기준으로 우, 상 방향으로 k만큼 이동하며 점을 찍는다.
// 우 방향으로 k만큼 이동하며 0부터 k씩 증가시키며 좌표가 d 거리 안에 있는지 확인한다.
// Math.sqrt 연산을 매 좌표마다 실행할 경우에 시간초과. O(n) = n^2
// x값에 따라서 최대 y값을 먼저 값을 지정하면 O(n) = n 으로 시간을 줄일 수 있다.
// 최대 y값이 나오면 maximum / k를 통해서 해당 x 값에 대해서 나올 수 있는 좌표의 개수가 나온다.
// 단, 위와 같이 개수를 세면 (x, 0)이 포함되지 않으므로 +1을 실행한다.
function solution(k, d) {
let result = 0
for(let x = 0; x <= d; x = x + k) {
const maximum = Math.sqrt(d*d - x*x)
result += Math.floor(maximum / k) + 1
}
return result
}