▶ 문제
두 정수 left와 right가 매개변수로 주어진다.
left 부터 right 까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고 약수의 개수가 홀수인 수는 뺀 수를 return 하는 solution 함수 만들기.
▶ 제한사항
1 ≤ left ≤ right ≤ 1,000
▶ 풀이
코드 그리기 끝! 이대로만 코드 짜기
def solution(left, right):
answer = 0
count = 0
for i in range(left, right+1):
for j in range(i//2 + 1):
if i % j == 0:
count += 1
if count % 2 == 0:
answer -= i
else:
answer += i
return answer
# ZeroDivisionError: integer division or modulo by zero틀림
0으로 나눌 수 없다? 내가 언제 0으로 나눴지 흠
아 두번째 for문에서 range의 시작범위를 지정안했더니 start가 자동으로 0으로 설정된 것 같다.
for i in range(left, right+1):
for j in range(1, i//2 + 1): # 시작 1로 지정시작을 1부터로 바꿔주고 다시 실행!
흠..
오류없이 실행은 되고 결과가 아무 규칙없이 틀린거 보면
들여쓰기나 코드 위치가 잘못된것같다?
찾음! 각 정수 시작할때마다 count가 0으로 초기화 되어야하니까
count 위치를 첫번째 for문 안으로 변경해준다
def solution(left, right):
answer = 0
for i in range(left, right+1):
count = 0 # 정수마다 count 초기화
for j in range(1, i//2 + 1):
if i % j == 0:
count += 1
if count % 2 == 0:
answer -= i
else:
answer += i
return answer오예 통과!
+
제곱수 이용하기
제곱수는 약수 개수가 홀수개, 제곱수가 아닌수는 짝수개 !!
맞다 약수 개수가 홀수인지 짝수인지 구할 때 제곱수 이용해서 풀 수 있었다.
약수끼리는 서로 곱해서 원래의 수가 되는 짝이 있기 때문에 짝수개다.
근데 제곱수일 경우 짝이 자기자신인 수가 한개 있기 때문에 홀수개다.
이점을 이용하면
def solution(left, right):
answer = 0
for i in range(left, right+1):
if int(i**0.5) == i**0.5:
answer -= i
else:
answer += i
return answer통과!
여기서 의문이 i**0.5 는 소수점으로 나눴으니 결과가 소수점(float)인데
어떻게 int 랑 비교를 할 수가 있냐는 거다.
심지어 float == int 결과가 true 로 나온다니? 납득할 수 없음
print(9**0.5) # 3.0
print(type(9**0.5)) # <class 'float'>
print(type(3)) # <class 'int'>
print(3.0 == 3) # True
print(type(3+6.0)) # <class 'float'>선샌미한테 물어본 결과
int 는 '연산과정' 에서 자동으로 float 으로 변경되어서 계산된다!
그래서 정수+소수점 덧셈도 가능한거
정수에 소수점 더할때마다 매번 에러뜨면 짜증나니까
파이썬이 친절하게 설정해놓은 기능이라구 한다.
== 도 비교연산자이니 int가 float 취급되어서 비교가능한거.
암튼 이렇게 제곱수 이용해서 풀면
for문이 중복에서 하나로 줄어들어 시간복잡도가 O(n^2)에서 O(n)이 된다
if문도 하나 줄어서 조건도 덜 거치게 됨
성능 비교해보기
우와 시간차이 대박많이 난다
이래서 머리를 써야되는구냐