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

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

프로그래머스

 

---

💻 풀이 결과

• 1차 채점 결과 : 60.0 (시간 초과)
• 2차 채점 결과 : 60.0
• 3차 채점 결과 : 100.0

💯 최종 코드

import java.util.*;

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        // x^2 + y^2 = r^2 공식을 이용해야 한다..
        for(int x = 0; x < r1; x++) {
            // 각 x 좌표별로 cnt 구하기
            double y2 = Math.sqrt(Math.pow(r2, 2) - Math.pow(x, 2));
            double y1 = Math.sqrt(Math.pow(r1, 2) - Math.pow(x, 2));
            
            // 사이 갯수 세기
            int cnt = (int)Math.floor(y2) - (int)Math.ceil(y1) + 1;
            
            answer += cnt;
        }
        
        for(int x = r1; x < r2; x++) {
            // 각 x 좌표별로 cnt 구하기
            double y2 = Math.sqrt(Math.pow(r2, 2) - Math.pow(x, 2));
            
            // 사이 갯수 세기
            int cnt = (int)Math.floor(y2);

            answer += cnt;
        }
        
        // 4개의 사분면이 똑같은 갯수
        answer *= 4;
        
        return answer;
    }
}

💢 틀린 이유

1. 시간 복잡도가 O(r²)

• 해당될 수 있는 범위의 정수 좌표들을 모두 탐색하면서 원점과의 거리가 r1 이상 r2 이하인 좌표들을 찾는 방법으로 로직을 짰다.
• r1과 r2의 범위가 1,000,000 이하이므로 시간초과가 발생했다.

틀린 풀이 과정

import java.util.*;

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        for(int x = 1; x < r2; x++) {
            for(int y = 1; y < r2; y++) {
                // 원점에서 (x, y)까지의 거리
                double dist = Math.sqrt((x * x) + (y * y));

                if(dist >= r1 && dist <= r2) {
                    answer++;
                }
            }
        }
        
        // 4개의 사분면이 똑같은 갯수
        answer *= 4;
        // x축과 y축에 접하는 점들 갯수
        answer += (r2 - r1 + 1) * 4;
        
        return answer;
    }
}

// 1차 채점 결과 : 60.0 (시간 초과)

2. int, long, double 자료형

• r2나 r1을 제곱하면서 자료형이 int 범위를 벗어나게 된다.
• Math.sqrt(제곱근), Math.ceil(올림), Math.floor(내림) 함수를 쓰면서 실수형으로 바뀌기 때문에 double 자료형으로 선언해야 한다.

💬 풀이 과정

• x² + y² = r²에 해당하는 (x, y) 좌표가 원 위에 있는 점이라는 공식을 사용해야 했다.
• 4개의 사분면에는 똑같은 개수의 조건을 만족하는 좌표들이 존재하기 때문에 하나의 사분면만 탐색하면 된다.
• 그래서 2 사분면 기준으로 x 좌표를 0부터 (r2- 1)까지 만족하는 y 좌표의 범위를 체크한다.
• x 좌표가 r1에 도착하기 전까지는 조건을 만족하는 개수가 (y2 - y1 + 1) 개다.
• x 좌표가 r1부터 r2에 도착하기 전까지는 조건을 만족하는 개수가 y2개이다.
• 하나의 사분면에 해당하는 개수 answer가 완성되면 4배 한다.

💡 깨달은 점

1. x² + y² = r²

• 다음 식에 해당하는 (x, y) 좌표가 원 위에 있는 점이다.

2. Math 라이브러리 함수

• Math.pow(숫자, 제곱수) : n제곱
• Math.sqrt(숫자) : 제곱근
• Math.ceil(숫자) : 올림
• Math.floor(숫자) : 내림