문제 설명
좌표평면을 좋아하는 진수는 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 함수를 완성하세요.
제한사항
1 ≤ k ≤ 1,000,000
1 ≤ d ≤ 1,000,000
내가 시도한 방법
문제를 보자마자 정말 간단해보여서 이게 왜 Lv.2에 있는거지? 싶었다.
d의 제곱과, 2중 for문으로 x와 y값이 증가하도록 한 값의 제곱의 합을 비교하기만 하면 되는거 아닌가? 하면서 코드를 작성해보았지만
당연하게도 예제문제만 성공하고 테스트 케이스에서는 완벽하게 시간초과...ㅎ
public class Test_85_MakingAPoint { // 점 찍기
public long solution(int k, int d) {
long answer = 0;
int distance = d * d;
// 2중 for문으로 a와 b가 증가할 때 d 이하인 좌표인 경우에만 추가
for (int x = 0; x <= d; x++) {
for (int y = 0; y <= d; y++) {
// d 이하의 거리인 좌표 확인은 (d의 제곱) >= (x의 제곱) + (y의 제곱)으로 확인
if ((x * k) * (x * k) + (y * k) * (y * k) <= distance) {
answer++;
}
}
}
return answer;
// ----------- 정확성 : 6.3 / 100.0 -> 실패(시간초과) -----------
// 시간복잡도 개선 필요!!
}
}제한사항의 k와 d값의 범위를 신경쓰지 않아서였다.
시간복잡도를 계산해보니
O((d+1)²)
최대 10^12번의 실행을 해야한다.
개선을 위한 고민
우선 범위가 광대하므로 이중 for문을 없애야하므로
x값을 고정하고 가능한 y의 최대 범위를 계산한다.
수학적 접근으로 x를 이항시켜 d와 함께 고정값 취급을 하고,
Math.sqrt로 루트를 씌운다.
public class Test_85_MakingAPoint { // 점 찍기
public long solution(int k, int d) {
long answer = 0;
for (int x = 0; x <= d; x += k) {
// x 좌표가 고정되었을 때, 가능한 y 좌표의 개수를 구함
// (x^2 + y^2 <= d^2) 이므로 y^2 <= d^2 - x^2
long maxY = (long) Math.sqrt((long)d * d - (long)x * x);
answer += (maxY / k) + 1; // 0부터 시작이므로 +1
}
return answer;
}
}개선된 코드로 시간복잡도를 계산해보니
O(d / k)
최대 10^6번 실행을 해야한다.
평소 알고리즘 문제를 해결할 때 시간복잡도에 대해서 고민을 잘 하는 편은 아니라서 문제가 너무 간단하다고 오해를 해버린 케이스
이제는 제한 범위를 확인해보고 시간복잡도 개선에 대한 고민을 해보는 습관을 들여야겠다.
