20240220_두 원 사이의 정수 쌍(프로그래머스)

오늘의 TIL은 대충 만든 자판이라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

 

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

프로그래머스

 

 

문제 설명

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 2개 주어진다.

반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때,

두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return 하시오.

 

각 원 위의 점도 포함한다.

 

 

제한 조건

1 <= r1 < r2 <= 1,000,000

 

 

해결 방안

1. 대칭성 이용

r2의 최대 값이 1,000,000이므로 모든 값을 구하면 매우 많은 값이 구해질 것이므로,

좌표축의 대칭성을 이용하여 x축과 1사분면에서 점의 개수를 구하고 4배 하는 것으로 구한다.

 

2. 좌표축과 원이므로 Math의 Pow, Sqrt, Ceiling을 이용

Pow는 거듭제곱(Math.Pow(double x, double y) = x의 y제곱)

Sqrt는 제곱근(Math.Sqrt(double x) = x의 제곱근)

Ceiling은 올림(Math.Ceiling(decimal x) = x보다 크거나 같은 제일 작은 정수값(10진수)

 

 

통과한 답안

using System;

public class Solution {
    public long solution(int r1, int r2) {
        
        long answer = r2 - r1 + 1;
        long r1Sqaure = (long)Math.Pow(r1, 2);
        long r2Sqaure = (long)Math.Pow(r2, 2);

        for (int x = 1; x < r2; x++)
        {
            long xSquare = (long)Math.Pow(x, 2);
            int yMax = (int)Math.Sqrt(r2Sqaure - xSquare);

            if (x < r1)
            {
                int yMin = (int)Math.Ceiling(Math.Sqrt(r1Sqaure - xSquare));
                answer += yMax - yMin + 1;
            }
            else
            {
                answer += yMax;
            }
        }

        answer *= 4;
        
        return answer;
    }
}

 

 

 

초기화 및 필요한 값들 정리

 

long answer = r2 - r1 + 1;
long r1Sqaure = (long)Math.Pow(r1, 2);
long r2Sqaure = (long)Math.Pow(r2, 2);

 

아래에서 계산할 때, 여러 번 계산하는 것을 방지하기 위해 각 원의 반지름의 제곱값을 저장한다.

이때, answer 가 long이므로 r1Sqaure, r2Sqaure도 long의 형식으로 만들어준다.

또, x축의 점들은 r2와 r1 사이의 점이므로, 정수인 r1과 r2 사이의 정수의 개수는 r2 - r1 + 1이다.

 

 

두 원 사이에 존재하는 정수인 점 찾기

for (int x = 1; x < r2; x++)
{
    long xSquare = (long)Math.Pow(x, 2);
    int yMax = (int)Math.Sqrt(r2Sqaure - xSquare);

    if (x < r1)
    {
        int yMin = (int)Math.Ceiling(Math.Sqrt(r1Sqaure - xSquare));
        answer += yMax - yMin + 1;
    }
    else
    {
        answer += yMax;
    }
}

answer *= 4;

 

for문을 사용하여 1부터 r2 미만까지의 모든 x에 대해서 x의 길이의 원을 그렸을 때,

이 원에서 r2의 원 내부에 있는 y의 개수(yMax)를 구하고 더해준다.

이 때, x 값이 r1보다 작은 경우에는 r1원 내부에 있는 y의 개수(yMin)을 계산하고 이를 빼준다.

 

여기서 구한 값은 1사분면의 값들을 구한 것이고,

위에서 초기화하면서 x축 위에 값을 구한 것이므로,

 

지금의 answer는 x축(+방향)과 1사분면의 값을 구한 것이므로 answer를 4배 해주므로써 답을 구할 수 있다.

(원점은 r1이 1보다 크기 때문에 빠지므로 고려하지 않는다)

 

 

 

오늘은 알고리즘 문제를 풀면서 수학적인 개념을 요구하는 문제를 발견하여 풀게되었는데,

 

처음에는 r1의 반지름을 갖는 원을 그리고 그 원보다 큰 정수값을 모두 구하는 방식으로 구현했었는데,

 

r2의 최대값이 너무 크기 때문에 시간 초과로 문제를 해결하지 못했었다.

 

특히 원의 특징을 사용하기 때문에 제곱을 하는 과정에서 많은 시간이 걸려 문제가 생겼었는데,

 

초기에 r1Sqaure, r2Sqaure를 미리 long 타입으로 구함으로써 시간을 단축할 수 있었다.

 

 

수학적인 사고와 함께 걸리는 시간과 관련하여 최적화적인 요소를 함께 고민할 수 있었던 문제였다.