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

이번 문제는 좌표평면 위의 원이 두 개가 주어지고, 해당 원 사이의 정수쌍인 좌표의 개수를 구하는 문제입니다. 처음 봤을 땐 진짜 어이없게 문제를 풀어보았는데, 당연히 틀렸고요. 여러 번 트라이를 한 이후에 풀 수 있었습니다. 그중에서 2가지 풀이를 소개해드리려고 하는데, 첫 풀이는 시간 초과가 나온 풀이법이고, 다음 풀이법은 정답처리된 풀이법입니다.

 

시간초과 풀이법

시간초과 풀이법은 브루트포스 방식으로 무식하게 풀려고 했습니다, 먼저 코드를 보도록 하겠습니다.

 

    for i in range(r2**2):
        if x**2 + y**2 >= r1**2 and x**2 + y**2 <= r2**2:
            answer += 1
        if x**2 + (y-1)**2 >= r1**2 and y > 1:
            y -= 1
        elif (x+1)**2 + y**2 >= r1**2 and x < r2:
            x += 1
            y = r2

    return answer*4

 

시간초과를 한 풀이법의 아이디어는 다음과 같습니다.

1. 두 개의 원 중에서 더 큰 원의 반지름과 한 변의 길이가 동일한 정사각형이 있다고 가정합니다. 

2. 만들어진 정사각형 내의 모든 정수쌍 좌표에 방문합니다.

3. 원의 방정식 x^2 + y^2 = r^2을 이용해서 방문한 좌표가 작은 원 R1과 큰 원 R2 사이에 위치하는지 확인합니다.

4. 1사분면만 방문하고, 대칭이라는 특성을 이용해 4를 곱해줍니다.

 

사실 제한조건이 안 쓰여 있어서 이런 방식으로 풀었지만, 10초가 시간제한이었고, 제가 푼 방식은 시간 복잡도가 O(n^2)이므로, 시간 초과가 뜬 것입니다.

 

정답 풀이법

def solution(r1, r2):
    answer = 0

    min, max = r1, r2

    for y in range(r2):
        while max**2 + y**2 > r2**2:
            max -= 1
        while min > 1 and (min-1)**2 + y**2 >= r1**2:
            min -= 1
        answer += max - min + 1 
    return answer*4

 

그래서 해결한 방법이 바로 이 방법입니다. 아이디어는 다음과 같습니다.

1. 원의 방정식을 이용해서 큰 원 R2와 접하거나, 작은 좌표 중 가장 큰 x좌표를 구해 max로 설정하고, 작은 원 R1과 접하거나, 큰 좌표 중 가장 작은 x좌표를 구해 min으로 설정합니다.

2.  min과 max 사이에 존재하는 x좌표들은 두 원 사이의 정수쌍에 해당하므로, 개수를 세줍니다.

3. 단, x좌표가 0인 부분까지 세면 중복으로 세지는 부분이 있으니, x좌표가 1일 때까지만 개수를 셉니다.

 

마치며

1일 1문제 풀이를 하는 중인데, 생각보다 시간도 오래 걸리고 어려운 것 같네요. 레벨 3은 풀 수 있어야 한다는데, 레벨 2에서도 허덕이는 것 같아서 이직을 할 수 있을지 모르겠습니다.