catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 점 찍기

jin@catsriding.com
Oct 14, 2024
Published byJin
999
프로그래머스 | Level 2 | 점 찍기

Programmers | Level 2 | 점 찍기

Problems

󰧭 Description

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

  • 원점(0, 0)으로부터 x축 방향으로 a*k(a = 0, 1, 2, 3 ...), y축 방향으로 b*k(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 함수를 완성하세요.

 Constraints

  • 1 ≤ k ≤ 1,000,000
  • 1 ≤ d ≤ 1,000,000

󰦕 Examples

kdresult
246
1526

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long dots = 0;  // 찍힌 점들의 총 개수
        for (int x = 0; x <= d; x += k) {
            int limit = (int) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2));  // x좌표에 대한 y좌표의 최대값 계산
            dots += limit / k + 1;  // 가능한 y좌표의 수를 더함
        }
        return dots;
    }
}

 Approaches

이 문제는 원점을 중심으로 하는 원 내에서 점을 찍는 문제로, 원의 방정식과 그리드 좌표의 특성을 이용해 해결할 수 있습니다. 원점으로부터의 거리를 계산하여 각 위치에 점을 찍을 수 있는지 확인하며, 이를 반복하여 전체 점의 개수를 구합니다.

1. 문제 분석

주어진 문제는 좌표 평면 상에서 원점 (0, 0)을 기준으로 특정 반지름 이내에 점을 찍는 문제입니다. 점의 좌표는 x축과 y축을 따라 각각 k 간격으로 찍을 수 있으며, 찍힌 점의 좌표는 (a * k, b * k) 형태로 나타납니다. 즉, x와 y 값은 각각 k의 배수여야 하고, 이러한 조건을 만족하면서도 원점에서의 거리가 반지름, 즉 d를 넘지 않도록 점을 찍어야 합니다.

이 문제는 수학적으로 원의 방정식과 관련이 있습니다. 원의 방정식은 다음과 같이 표현됩니다:

x^2 + y^2 = r^2

이 방정식은 원점에서 거리 r만큼 떨어진 점 (x, y)들이 원의 경계에 있는 점임을 나타냅니다. 이 문제에서는 원의 경계뿐만 아니라, 원 내부에 포함된 점들도 구해야 합니다. 주어진 x 값에 대해 가능한 y 값은 원의 방정식을 통해 구할 수 있으며, 이를 통해 x와 y가 원의 내부에 위치하는지를 확인합니다.

따라서 문제의 해결 핵심은 다음과 같습니다:

  • x 값을 k 간격으로 증가시키면서 가능한 y 값을 찾습니다.
  • 각 x에 대해, 주어진 반지름 d을 넘지 않는 y 값을 원의 방정식으로 계산하여 점을 찍습니다.

이 문제는 좌표 평면에서 주어진 조건에 따라 찍힌 점들의 수를 구하는 문제로, 원의 방정식을 활용해 효율적으로 해결할 수 있습니다.

2. 접근 방식

이 문제는 원의 방정식과 좌표 평면을 기반으로 주어진 거리 d 이내에서 k 간격으로 점을 찍는 과정을 통해 해결할 수 있습니다. 문제를 해결하기 위한 접근 방식은 다음과 같습니다:

  1. 반복적 좌표 계산: x축을 따라 k 간격으로 점을 이동하면서 각 x 값에 대해 가능한 y 좌표의 최대값을 구합니다. 이는 주어진 거리 d를 만족하는 y좌표를 계산하는 과정입니다. 원의 방정식을 사용하여 해당 x에 대해 찍을 수 있는 y좌표의 범위를 구합니다.
  2. 원의 방정식 활용: 주어진 x 값에 대해 계산된 y 값은 해당 좌표에서 찍을 수 있는 최대 거리 내에서의 값입니다. 이때, 구한 y 값은 원의 경계까지의 거리를 의미하며, y가 k 간격으로만 찍히기 때문에, 가능한 y 좌표는 k의 배수로 제한됩니다. 즉, y 값은 k로 나눈 몫으로 가능한 점들의 수를 구할 수 있습니다.
  3. 그리드 간격에 맞는 점 계산: 각 x 값에 대해 구한 y 값은 k의 배수로 찍을 수 있는 점의 수를 나타냅니다. 따라서 가능한 y 좌표의 개수를 구한 후, 이를 누적하여 총 찍힌 점의 개수를 계산합니다. x축을 기준으로 k 간격으로 움직이면서 각 좌표에서 가능한 y 좌표들을 계산하고, 그 수를 모두 합산합니다. 예시로, x = 0일 때는 y = d에 해당하는 값에서 k 간격으로 점을 찍을 수 있으며, x가 증가할수록 가능한 y 값은 줄어들게 됩니다.

이 접근 방식을 통해, 원점에서 거리 d 이내의 좌표평면 상에서 k 간격으로 찍을 수 있는 점들의 총 개수를 계산할 수 있습니다.

3. x좌표에 따른 y의 최대 범위 계산

x축을 따라 0부터 d까지 k 간격으로 이동하면서 각 x 좌표에 대해 가능한 y 좌표의 최대값을 계산합니다. 이 과정은 효율적인 점 계산을 위해 필요합니다. 즉, 각 x 좌표에 대해 y의 최대 범위를 미리 계산함으로써, 해당 범위 내에서 가능한 점들의 수를 빠르게 파악할 수 있습니다. 이렇게 하면 불필요한 좌표 계산을 줄여 성능을 향상시킬 수 있습니다.

x 값이 커질수록 y 좌표의 범위는 줄어드므로, 각 x 좌표에서 가능한 y 좌표의 최대값을 계산한 후, 해당 범위 내에서 찍을 수 있는 점을 k 간격으로 효율적으로 계산하게 됩니다.

Solution.java
for (int x = 0; x <= d; x += k) {
    double dSquared = Math.pow(d, 2);  // 원의 반지름의 제곱 계산
    double xSquared = Math.pow(x, 2);  // 현재 x 좌표의 제곱 계산
    int limit = (int) Math.sqrt(dSquared - xSquared);  // 원 방정식에 따라 y 좌표의 최대값 계산
    ...
}

각 x 좌표에서 계산된 y 좌표의 최대값을 통해, 해당 x 좌표에서 찍을 수 있는 점들의 수를 이후에 계산하게 됩니다.

4. 가능한 y좌표를 통한 점의 개수 계산

계산된 y 좌표 값은 주어진 거리 d 내에서 찍을 수 있는 최대 y 좌표의 범위를 나타냅니다. 그러나 점을 찍을 수 있는 위치는 k 간격으로 제한되기 때문에, y 값에서 k의 배수인 위치들만 유효한 점으로 간주됩니다. 따라서, 계산된 y 좌표 값을 k로 나누어, 그 몫만큼 가능한 점의 개수를 구할 수 있습니다.

예를 들어, y 값이 15이고 k가 5라면, y 값 내에서 k의 배수인 0, 5, 10, 15에서 점을 찍을 수 있습니다. 여기서 원점 (x, 0)도 유효한 좌표이므로, 총 가능한 좌표의 개수는 y 값을 k로 나눈 몫에 1을 더해줍니다.

즉, 각 x 좌표에서 찍을 수 있는 점의 개수는 y 값을 k로 나눈 몫에 1을 더한 값으로 구할 수 있습니다.

Solution.java
for (int x = 0; x <= d; x += k) {
    ...
    // y 좌표의 최대값을 k로 나누어 가능한 점의 개수를 계산
    dots += limit / k + 1;  // limit은 y 좌표의 최대값, 가능한 y 좌표의 수를 누적
}

이러한 방식으로, 각 x 좌표에 대해 가능한 y 좌표의 개수를 구하고, 그 값을 모두 더하여 전체 찍을 수 있는 점의 개수를 계산할 수 있습니다. x 값이 커질수록 y 좌표의 범위는 줄어들기 때문에, 찍을 수 있는 점의 개수도 줄어듭니다.

󰄉 Complexity

  • ⏳ TC: O(n)
  • 💾 SC: O(1)

x좌표를 k 간격으로 이동하면서 가능한 y좌표를 계산하므로, 전체 시간 복잡도는 거리 d를 k로 나눈 값에 비례합니다. 이는 d가 최대 1,000,000까지 가능하므로, 매우 효율적인 방식으로 해결할 수 있습니다.

  • Algorithm
  • Math