[프로그래머스] 두 원 사이의 정수 쌍

문제 주소

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

프로그래머스

문제 설명

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.

※ 각 원 위의 점도 포함하여 셉니다.

---

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

---

입출력 예

r1 r2 result

2

3

20

 

제출 코드

import java.lang.Math;

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        long l1 = (long)r1;
        long l2 = (long)r2;
        
        for(long x = 1; x <= l2 ; x++){

            long right = (long)Math.floor(Math.sqrt(l2*l2-x*x));
            long left = (long)Math.ceil(Math.sqrt(l1*l1-x*x));
            long number = right-left+1;
            answer += number;
        }
        answer *= 4;
        return answer;
    }
}

 

 

풀이과정

원이니까 x의 제곱의 합과 y의 제곱의 합이 r의 제곱보다 작은 경우를 본다고 보면 될듯?

1사분면과 -x축 + y축만 세어가지고 4배 해주면 될 거 같음

 

x는 1부터 y는 0부터

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        for(long x = 1;x <= r2 ; x++){
            for(long y = 0; y<=r2; y++){
                long square = x*x + y*y;
                if(square>=r1*r1&&square<=r2*r2){
                    answer++;
                }
            }
        }
        answer *= 4;
        return answer;
    }
}

 

이렇게 냈더니 시간초과가 남

테스트 1 〉	통과 (0.06ms, 82.8MB)
테스트 2 〉	통과 (0.08ms, 78.2MB)
테스트 3 〉	통과 (0.12ms, 78.4MB)
테스트 4 〉	통과 (9.63ms, 74.4MB)
테스트 5 〉	통과 (9.30ms, 77.7MB)
테스트 6 〉	통과 (20.19ms, 75.9MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

 

저런 문제 코테에서 만나면 조심해야겠다

전에 삼각형의 정점 세는 문제도 그렇고 그냥 무의식중에 제곱으로 for문 2번 돌려서 풀게되는데 

그러면 제출했을때 테스트케이스에서 점수 많이 까일 것 같다

 

더 빠른 방법 생각해 보다가 Math.square의 값을 floor를 하거나 ceil을 해서 빼보면 될 것 같다고 생각함

import java.lang.Math;

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        for(long x = 1; x <= r2 ; x++){

            int right = (int)Math.floor(Math.sqrt(r2*r2-x*x));
            int left = (int)Math.ceil(Math.sqrt(r1*r1-x*x));
            long number = right-left+1;
            System.out.println(right+"-"+left+"="+number);
            answer += number;
        }
        answer *= 4;
        return answer;
    }
}

테스트 1 〉	통과 (0.33ms, 72.1MB)
테스트 2 〉	통과 (0.28ms, 71.6MB)
테스트 3 〉	통과 (0.39ms, 74MB)
테스트 4 〉	통과 (1.16ms, 77.3MB)
테스트 5 〉	통과 (0.86ms, 81MB)
테스트 6 〉	통과 (1.66ms, 67.3MB)
테스트 7 〉	실패 (13.28ms, 82.3MB)
테스트 8 〉	실패 (22.62ms, 73.5MB)
테스트 9 〉	실패 (11.80ms, 77MB)
테스트 10 〉	실패 (15.35ms, 81.9MB)

저 실패는 아마 overflow 문제라고 생각하고 long으로 만들어줬더니 통과함

        long l1 = (long)r1;
        long l2 = (long)r2;
        
        
        ...
        
        
        long right = (long)Math.floor(Math.sqrt(l2*l2-x*x));
            long left = (long)Math.ceil(Math.sqrt(l1*l1-x*x));

 

어떤 사람은 r1*r1*0.0, x*x*0.0을 곱해서 double화 하기도 함

int로 넣으면 overflow 일어나고 double이나 long으로 캐스팅해서 넣어줘야 하는 것 같음