프로그래머스 - 점 찍기 (Java)

 

문제 개요

 

문제 설명

 

제한사항 및 입출력 예

 

 

---

 

풀이

 

아무튼 단순 구현이기 때문에 정답을 도출하는 방법은 되게 간단하게 보인다.

 

바로 2중 for문을 사용해서 x나 y 중 하나를 기준으로 잡고, (0, 0), (0, k), (0, 2k),,, (k, 0), (k, 2k), (k, 2k) 이런 식으로 첫 for문은 0부터 d까지 k 씩 증가시키고, 두 번째 for문도 동일하게 0부터 d까지 k씩 증가시키면서 거리가 멀어지면 break 하고 카운팅하면서 넘어가도록 구현하면 정답은 구할 수 있을 것이다.

 

그런데 이렇게 풀면 효율성에서 탈락된다. 역시 Level 2라서 그런지 그냥 풀수는 없나 보다.

 

2중 for문을 사용해서 효율성에서 떨어졌으니 for문을 1번만 쓰면서 문제를 풀면 된다. 그렇다면 어떻게 한번만 사용해서 풀 수 있느냐가 이게 관건이다.

 

다시 한 번 문제를 돌아보면 문제에서 요구하는 것은 원점부터 특정 포인트의 거리가 d 이하인 점들 중, x와 y가 각각 k로 나눠지는 점의 개수(?)를 구하면 되는 것이다.

 

 

여기서 '거리'에 초점을 맞춰 생각해 보자.

일반적으로 거리를 구하는 공식은 (x1 - x2)^2 + (y1-y2)^2이다. 그런데 여기서는 원점부터 특정 점 (x, y)까지의 거리가 d보다 작아야 한다는 조건이 붙었기에 x^2 + y^2 < d^2와 같이 표현할 수 있다.

 

여기서 d는 문제에서 주어진 값이고, 우리가 for문을 한 번만 돌면서 루프 변수를 x로 두고 루프를 돌린다고 했을 때, d^2 - x^2의 제곱근을 구하고, 해당 값을 넘지 않는 최대의 정수를 구한다면, 그 값이 d와 x를 알 때 y의 최대 값이 되는 것이다.

 

x로 루프를 돌리면서 y의 최대 값을 구했다면, 반복문을 사용해서 각각의 x에서 y의 최댓값을 넘지 않는 k의 배수의 개수를 누적하여 answer에 넣어서 리턴해주면 끝난다.

 

---

 

코드

 

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        long limit = (long) Math.pow(d, 2);
                
        for (long a=0 ; a<=d ; a=a+k) {
            long b = (long) Math.sqrt(limit - Math.pow(a, 2));
            answer += b/k+1;
        }
        
        return answer;
    }
}

 

혹시나 for문에서 b / k + 1을 더해주는 이유는 아래와 같다.

• 문제 지문에 나왔듯이 x와 y가 k씩 떨어진 점의 갯수를 구해야 하기 때문이다.
• 원점 (0, 0)부터 시작하기 때문에 1을 더해줘야 하기 때문이다.

 

---

 

제출 결과

 

 

내가 인텔리제이 IDE로 작성한 코드는 깃허브(여기 링크)에 올려두었다.