[프로그래머스] Lv.2 점 찍기 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/140107

프로그래머스

 

문제 설명

진수는 두 양의 정수 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,2), (4,0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution함수를 완성해 주세요.

---

💡 T I P

d와 k의 범위가 최대 1,000,000까지 나올 수 있으므로 이중 반복문을 사용하면 분명히 시간초과가 걸릴 것입니다.

따라서 이중반복문을 사용하지 않고 구하는 방법을 찾아야 합니다.

 

📗 풀이과정

1. 예시 k=2, d=4인 예시를 보면 좌표를 구했을 때 나오는 점을 좌표평면으로 구현해 보면 아래와 같습니다.

예시에 해당하는 점들을 보면 y좌표가 점점 증가함에 따라 x좌표는 줄어들거나 유지하는 것을 확인할 수 있습니다.

따라서 x좌표가 나올 수 있는 가장 큰 값을 먼저 구하고, 거기서 y가 증가함에 따라 유지하거나 줄이면 됩니다.

 

2. 일단 x좌표가 나올 수 있는 최댓값을 구합니다. (d보다 작은 k의 배수)

 

3. 해당 점에서 (0,0)까지 0을 포함해 k의 배수가 총 몇 개 있는지 세서 answer에 더해줍니다.

현재 x좌표=4

answer+= x/k + 1 (+1은 (0,0)을 포함하기 위해서 해줍니다.)

4. 그리고 그다음 지점부터는 (x, y)과 원점과의 거리가 d이하일 때만 answer에 추가할 수 있기 때문에, 

다음 y좌표에서 점을 찍을 수 있는 x좌표를 구해줍니다.

다음 y좌표는 1*k=2일 때, 거리가 d이내 인 x좌표를 구해서  answer에 개수를 더해줍니다.

5. 위와 같이 y좌표가 처음 x좌표와 같이 d보다 작은 k의 배수일 때까지 개수를 구해 answer에 더해주고, 

answer를 return 합니다.

---

전체 코드

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        
        int maxCoor=0;// a,b가 나올 수 있는 최대 좌표
        for(int i=d;i>=1;i--){
            if(i%k==0){
                maxCoor=i;break;
            }
        }
        
        int b=maxCoor;
        for(long a=0;a<=maxCoor;a+=k){
            // Math.sqrt((a*k)^2 +(b*k)^2* <= d가 될 때까지 b를 찾음
            //제곱근 처리해주지 않으면 long형 범위를 벗어날 수 있어서 조심.
            while(Math.sqrt(Math.pow(a,2)+Math.pow(b,2)) > d){
                b-=k;
                //System.out.println(b);
            }
            answer+=b/k+1;// +1은 (b=0일 때까지 셈.)
            //System.out.println(a+" "+b+" : "+answer);
        }
        
        return answer;
    }
}