[코딩테스트] 두 원 사이의 정수 쌍

1. 풀이 방법

1. 모든 좌표를 검사하기 - 시간 초과

2. 해당 x좌표에서 가질 수 있는 y좌표의 최소, 최대 정수 값을 구하기 - 통과

 

2. 후기

역시...모든 좌표를 검사하는 풀이는 안된다...

 

풀이 코드

(1)

def solution(r1, r2):
    answer = 0
    minY, maxY = r1,r2 #최소, 최대로 가질 수 있는 y좌표
    
    # 1사분면에 대해서만 좌표값을 구하고 대칭이므로 *4한다.
    for x in range(0,r2):
        while r2**2 < maxY**2 + x**2:
            maxY -= 1
            
        # minY 양수값을 유지 
        while minY-1 and r1**2 <= (minY-1)**2 + x**2:
            minY -= 1
            
        answer += (maxY-minY) + 1
    
    return answer*4

해당 코드는 입력으로 주어진 두 원의 중심을 원점으로 놓고, 원의 반지름을 r1, r2라 할 때, 두 원의 중심을 연결하는 직선이 x축과 이루는 각이 0~90도에 해당하는 부분의 좌표를 구하는 함수입니다.

 

이를 위해 minY와 maxY를 초기값으로 설정하고, 이를 이용해 y좌표의 범위를 설정합니다. for문을 이용해 x좌표가 0부터 r2까지 변할 때, 해당 x좌표에서의 y좌표의 범위를 설정합니다.

 

먼저 while r2**2 < maxY**2 + x**2이 참인 동안 maxY값을 1씩 감소시키며 y좌표 범위를 조정합니다. 다음으로 while minY-1 and r1**2 <= (minY-1)**2 + x**2이 참인 동안 minY값을 1씩 감소시키며 y좌표 범위를 조정합니다.

 

마지막으로, (maxY-minY) + 1을 answer에 더해주고, 모든 x좌표에 대해 이를 반복하며 총 좌표의 개수를 계산합니다. return answer*4를 통해 대칭성을 고려하여 총 개수를 구합니다.

 

1. 변수 'answer'를 0으로 초기화합니다.

2. 변수 minY와 maxY를 r1과 r2로 초기화합니다. 이 변수들은 원의 위와 아래를 각각 가장 멀리 떨어져 있는 점으로 초기화됩니다.

3. x좌표가 0부터 r2-1까지의 값을 가질 수 있는 범위에서 반복문을 돌면서 아래를 수행합니다.

4. 변수 maxY를 하나씩 줄이면서 r2의 제곱보다 작은 값이 나올 때까지 반복합니다. 이 때 maxY는 y좌표의 최댓값이 됩니다.

5. 변수 minY를 하나씩 줄이면서 r1의 제곱보다 작은 값이 나올 때까지 반복합니다. 이 때 minY는 y좌표의 최솟값이 됩니다. 만약 minY가 0이라면 더 이상 minY를 줄일 수 없습니다.

6. answer에 (maxY-minY) + 1을 더합니다. 이는 x좌표가 x인 직선상에서 y좌표가 minY부터 maxY까지의 정수 좌표들을 포함한 점의 개수입니다.

7. 3-6번을 반복하면서 answer값을 누적합니다.

8. 모든 반복이 끝난 후 answer에 4를 곱하여 반환합니다. 이는 r1과 r2가 음수인 경우를 고려하여 1사분면에서 구한 점들을 대칭적으로 전체 평면에 대입한 값입니다.

 

 

(2)

from math import sqrt

def solution(r1, r2):
    quar = 0
    for i in range(0, r2):
        quar += int(sqrt(r2**2 - i**2)) - int(sqrt(max(0, r1**2 - i**2 - 1)))
        
        print(quar)
        
    return quar * 4

1. 반지름 r2를 기준으로 1사분면 상단의 좌표(0, r2)부터 시작하여
    아래로 이동하면서 x, y 좌표 모두 정수인 점을 찾습니다.

2. 각 x좌표마다, 반지름 r2 내에 있는 모든 y좌표를 찾습니다.

3. 먼저, 해당 x 좌표에서 y를 r2까지 증가시키며 반지름 r2 내의 좌표를 찾습니다.

4. 이후, r1을 고려합니다. r1은 r2보다 작거나 같은 값이기 때문에, 해당 x 좌표에서 y를 r2까지 증가시키며, 반지름 r1 내의 좌표를 찾습니다.

 

5. 따라서, 해당 x 좌표에 대한 정수 좌표 개수는 (r2 내의 정수 좌표 개수) - (r1 내의 정수 좌표 개수)로 구할 수 있습니다.

6. 각 x 좌표마다 구한 정수 좌표 개수를 총합하면, x, y 좌표 모두 정수인 점의 총 개수가 됩니다.

7. 마지막으로, 1사분면 하단부와 대칭하여 전체 좌표 개수를 구하기 위해 총 개수에 4를 곱합니다.