[프로그래머스] [Python] (Level 2) 두 원 사이의 정수 쌍

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

프로그래머스

 

 

문제

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

 

입출력( + 추가적인 Test Case)

r1	r2	result
2	3	20
20	30	1576
200	300	157088
20000	30000	1570796144

 

 

제한사항에 대해 보고싶으면 눌러주세요

제한사항

1 ≤ r1 < r2 ≤ 1,000,000

풀이방법

1. 한 사분면에 대해 두 원 사이에 있는 점을 구한 뒤에 4를 곱하면 총점의 개수입니다.

2. x는 1부터 r2(큰원까지) 순회하면서 점을 구합니다.

* 각각의 x에 대해서 총 2가지 case(큰 원 위에 점이 있는 경우와 없는 경우)가 존재합니다.

3. x가 r1 보다 작을 때입니다.

  3-1 r2 안에 있는 점들을 모두 구합니다. (이때 r2 원 위에 점이 있는지 없는지를 구합니다.) 

  3-2 r1 안에 있는 점들을 구한뒤 r2 점 개수 - r1 점 개수를 하고 총합에 더합니다.

4. x가 r1 과 같거나 큰 경우입니다.

  4-1 r2 밑에 있는 점들을 구한 뒤 총합에 더합니다.

5. 점의 총합에 4를 곱한 뒤 반환합니다.

 

x=4 일때 원 사이의 있는 점들을 구하고 있는 예시이다.

코드

from math import isqrt


def solution(r1, r2):
    r2_dots = 0
    # x 좌표로 계산
    for x in range(1, r2 + 1):
        y2 = isqrt(r2 ** 2 - x ** 2)

        # x와 평행한 선을 기준으로 r1과 r2가 모두 걸칠 때
        if x < r1:
            y1 = isqrt(r1 ** 2 - x ** 2)
            # 선 위에 점이 있는 경우
            if r1 ** 2 - x ** 2 == y1 ** 2:
                y1 = y1 - 1

        else:
            y1 = 0
            r2_dots += 1

        r2_dots = r2_dots + y2 - y1
    # 상하좌우 대칭이므로 4를 곱한다.
    return r2_dots * 4

결론

for 문 하나 만으로 풀 수 있는 간단한 문제였다. 시간복잡도가 O(n)이다.

처음에 dp를 생각해서 풀었지만, 계속 오류가 발생했다. 그 이유는 원 위에 있는 점들을 계산하지 못하면서 오류가 발생했다.

원 위에 있는 점들을 생각하면서 위와 같은 식들을 생각해 냈다.

1. 원 위에 점이 있는지 없는지를 구하는 것

2. 원은 상하좌우 대칭이기에 한 사분면만 구하고 4를 곱해서 시간을 아낄 것

두 가지를 생각해 내서 푼 문제였다. 처음에 접근하는데 시간이 오래 걸려서 1시간 넘게 풀었던 문제다.