[프로그래머스] 연습문제(LV2) : 두 원 사이의 정수 쌍

<문제출처>

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

프로그래머스

 

원점을 중점으로 가지는 두개의 원이 있을 때, 두개의 원 사이에 있는 정수 좌표 개수를 구해라!

 

<고민 끄적끄적>

접근1. 완전탐색 -> x O(n**2)
접근2. 1/4만 구하자 -> x 시간초과
접근3. 규칙을 찾아볼까? -> 실패
접근4 -> 큰 원안의 개수에서 작은 원안의 개수를 뺀다.

반지름값이 터무니 없이 컸기 때문에 사실 for문 한번에 해결할 수 있는 방법을 생각해 냈어야 했다.

x**2 + y**2 <= r**2 공식을 사용하면 x가 고정되었을 때 y의 좌표 범위를 특정할 수 있다.

최종적으로 큰 원안의 개수에서 작은 원안의 개수를 뺀다.
그리고 주의할 점은 작은 원의 경계에 존재하는 정주좌표의 개수를 구해서 더해줘야 한다는 것이다.

 

 

최종코드

# 반지름이 r인 원 안에 점이 몇개있는가
# x**2 + y**2 <= r**2
def find(r):
    ans = 0
    for x in range(-r, r + 1):
        abs_y = int(((r**2) - (x**2))**0.5)
        ans = ans + abs_y * 2 + 1
    return ans


def find_boundary(r):
    ans = 0
    for x in range(-r, r + 1):
        abs_y = ((r**2) - (x**2))**0.5
        if abs_y == 0:
            ans += 1
        elif int(abs_y) == abs_y:
            ans += 2
    return ans
    

def solution(r1, r2): 
    return find(r2) - find(r1) + find_boundary(r1)

도형 문제로 원의 특징을 알고 있었다면(?) 금방 접근할 수 있었을 것 같다.