업데이트 사항
수정 : 2024-07-10 [시간 복잡도 추가]
x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.
제한 사항
- 1 ≤ r1 < r2 ≤ 1,000,000
입출력 예
r1 r2 result
| 2 | 3 | 20 |
입출력 예 설명
그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다
코딩테스트 연습 - 두 원 사이의 정수 쌍 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
나의 코드
def solution(r1, r2):
answer = 0
for i in range(1, r2+1):
for j in range(r2+1):
now_len = (i**2+j**2)**(1/2)
if r1<=now_len<=r2:
answer+=1
if now_len>=r2:
break
answer*=4
return answer
# 시간 복잡도
이차형 시간복잡도.. ( O(n**2) )
수정 코드
# 2024-07-10
import math
def solution(r1, r2):
answer = 0
for x in range(r2):
max_y = int(((r2**2)-(x**2))**(1/2))
if r1<=x:
min_y=1
else:
min_y = math.ceil(((r1**2)-(x**2))**(1/2))
answer+=(max_y-min_y+1)
answer*=4
return answer# 시간 복잡도
for x in range(r2) : r2의 값으로 루프를 한바뀌 돔 ( 선형 시간 )
내부계산 : 상수시간
시간복잡도 : 선형시간 ( O(n) )
