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

1. 문제정의

 반지름이 r1인 작은 원과, r2인 큰 원이 존재한다. 이 두 원을 겹치면 작은원과 큰원 사이에는 일부 면적이 발생한다. 이 면적안에 있는 정수로 이루어진 좌표를 구하는 문제이다.

 

2. 내가 한 시도

 lv2로 올라오고 나서 부터는 문제를 봤을 때 어떻게 풀어야지! 라는 것이 잘 떠오르지 않게 되었다. 검색을 통해 이 문제는 피타고라스의 정리를 이용하면 쉽게 풀리는 문제라는 것을 알고나서 그 방향으로 해결법을 고민하기 시작하였다.

 

1번째 시도

  피타고라스의 정리를 이용해서 원 안에 있는 모든 점을 서치하여 조건에 맞는 점들만 리턴하도록 코딩하였다. 말 그대로 무식하게 모든 점을 서치해봤다.

 결과는 실패했다. 일부 테스트 케이스에서는 성공이었지만 일부에서는 시간초과가 발생하였다.

 

2번째시도

 이번에는 모든 점을 피타고라스의 식에 맞는지 비교하는 것이 아니라, 피타고라스 식을 이용해서 원의 경계값을 구하고, 올림하거나 내림하는 방식으로 구현하였다.

 작은원의 제곱 - 한변(x좌표)의 길이의 제곱의 계산결과는 나머지 한변의 길이 제곱의 값이 나온다. 즉, x좌표로 부터 수직으로 직선을 올렸을 때 원과 접하는 값이다. 이렇게 x좌표 기준으로 y값들을 구해주고, 작은원일 경우 올림, 큰 원일 경우 내림을 하게 되면 두 원사이에 있는 정수값들이 구해진다.

 결과는 모든 테스트 케이스를 통과했다.

3. 코드

public class Solution {

    public long solution(int r1, int r2) {
        long answer = 0L;

        /*
         * 한사분면의 점들만 구할 것이기 때문에 x가 0일 경우는 제외.
         */
        for (int i = 1; i <= r2; i++) {
            /*
             * 작은원의 제곱 - 한변의 길이의 제곱 을 계산해준 값은 나머지 한변의 길이 제곱의 값, 즉 해당 x좌표의 작은 원의 경계값.
             * 경계 값을 루트씌워주고 올림하면 작은 원의 바깥쪽에서 경계 값과 가장 가까운 정수 값이 됨
             */
            double v = Math.pow(r1, 2) - Math.pow(i, 2);
            Double ceil = Math.ceil(Math.sqrt(v));

            /*
             * 이번에는 큰 원의 제곱 - 한변의 길이의 제곱을 하게 되면 나머지 한변의 길이의 제곱의 값, 즉 해당 x좌표의 큰 원의 경계값.
             * 경계 값을 루트씌워주고 내림하면 큰 원의 안쪽에서 경계값과 가장 가까운 정수값이 됨.
             */
            double v1 = Math.pow(r2, 2) - Math.pow(i, 2);
            Double floor = Math.floor(Math.sqrt(v1));

            /*
             * 위에서 구한 두 값들이 우리가 구할 점들 이므로 서로 빼준다. 이상, 이하 계산이기 때문에 차에 +1을 해줌.
             */
            answer += floor.longValue() - ceil.longValue() + 1;
        }

        return answer * 4;
    }
}

 

4. 깨달은 점 

 이번에는 딱 문제만 봤을 때는 쉬운데? 라고 접근했다가 피타고라스 정리라는 녀석에게 얻어 맞아 버렸다. 역시 lv2문제는 쉬운 문제가 없는 듯 하다. 더욱 많은 문제를 풀고 많은 패턴에 익숙해질 수 있도록 노력해야겠다.