[프로그래머스 / Java] 점 찍기

 

첫번째 풀이

import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        for(int a=0; a<= d; a += k) {
            for (int b=0; b <= d; b += k) {
                int length = (a*a + b*b);
                if (length <= d*d) {
                    answer++;
                }
            }
        }
        return answer;
    }
}

 

결과

 

시간초과 몇개와 다수의 실패가 보인다.

제한 사항의 k와 d의 길이가 100만이여서 시간초과가 뜨는 것 같다.

이 방식은 계속 시간복잡도가 클거 같아 다른 방식을 생각해보았다.

 

 

두번째 풀이

import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;

        for(int a=0; a<= d; a += k) {
            for (int b=a; b <= d; b += k) {
                int length = (a*a + b*b);
                if (length <= d*d) {
                    if(a == b) {
                        // 대각선이면 +1
                        answer++;
                    } else {
                        // 한쪽이면 반대쪽도 같이(+2)
                        answer += 2;
                    }
                } else {
                    // 길이 넘어가면 멈춤
                    break;
                }
            }
        }
        return answer;
    }
}

 

결과

일단 시간초과 문제는 해결하고 테스트 수행 속도도 반으로 줄었다.

 

세번째 풀이

하도 안풀려서 곰곰히 생각해보았다.

기존 생각은 하나하나 찍어서 거리계산 하고 그 거리보다 작으면 더하고 넘어가면 break 하는 방식...

 

가만히 생각해보니

x가 특정 값일 때 y가 올 수 있는 최대값은 d^2 - x^2 이다.

그리고 k씩 증가하니까 최대값 / k 이면 갯수가 나오지 않을까?

이렇게 하면 2중 for문을 할 필요가 없다!

import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;

        for (int x = 0; x <= d; x += k) {
            // y의 최대값을 계산
            int maxY = (int) Math.sqrt((long) d * d - (long) x * x);
            // 가능한 y 값의 개수를 세고 더하기
            answer += (maxY / k) + 1;
        }
        return answer;
    }
}

 

결과

 

통과!

 

막힐 때는 생각의 전환이 필요한거 같다