[프로그래머스] #14 약수의 합 (MB, ms 성능확인)

▶ 문제

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수 만들기

 

▶ 제한사항

n은 0 이상 3000 이하인 정수

 

▶ 풀이

정수 n을 1부터 자기 자신까지로 하나씩 돌아가면서 나눠준 다음, 그 중에서 나머지가 0일 경우에만 변수 answer 에다가 하나씩 더해주면 끝!

def solution(n):
    answer = 0
    for i in range(1,n):
        if n % i == 0:
            answer += i
    return answer			# 틀림..

틀림

 

근데 이번엔 오류코드가 뜨는 것도 아니고 정상 작동하는데 그냥 틀렸다.ㅠ

킹받는 이모티콘

 

어 근데 결과를 읽어보니까 나의 (틀린)결과값에 뭔가 규칙이 있다.

정답보다 n 만큼 작은 숫자가 나온다는 것! (28-12=16, 6-5=1)

 

아하 내가 n으로는 나누기를 시행 안하고 있었다.

range(start, stop) 함수는 start  '이상' stop '미만' 의 범위를 지정한다

는 사실을 잊지말자. 제발 stop은 not include다. 제발 그만까먹자!

def solution(n):
    answer = 0
    for i in range(1,n+1):	# n+1 미만까지로 범위 변경
        if n % i == 0:
            answer += i
    return answer

오예 통과!

 

+

 

다른사람 풀이 구경하다가

n의 약수를 구할 때 n의 절반이 넘어가는 숫자들로는 나눠볼 가치가 없다

라는 사실을 깨닫게 되었다. 지금은 별거 아니지만 n이 엄청 큰 데이터라고 가정하면 계산 시간이 절반으로 줄어드는거니까 엄청 이득 아닐까? 이런 기본적인 생각을 왜 못했지

 

내가 컴퓨터한테 시킨 계산의 절반이 헛수고라는 것을 알게 되었는데 모른 척 할 순 없으니까 내가 조금 수고해서 코드를 수정해준다. n의 절반 이하만 계산하고, 자기자신 n은 따로 더해주기.

def solution(n):
    answer = n                   # 자기자신은 무조건 약수
    for i in range(1,n/2+1):     # n의 절반까지로 범위 변경
        if n % i == 0:
            answer += i
    return answer
    
# TypeError: 'float' object cannot be interpreted as an integer

float이 뭔데ㅜ 

 

찾아보니깐

float은 소수점이 있는 수라고 한다.

2로 나누면 n이 홀수인경우 0.5가 존재해서 정수로 해석이 안되니 범위를 잡을 수가 없었던 것!

그럼 몫에 해당하는 부분만 반환해주는 연산자 // 로 바꿔준다.

def solution(n):
    answer = n
    for i in range(1,n//2+1):	# 정수부분만 반환
        if n % i == 0:
            answer += i
    return answer

오예 통과!!!

 

 

진짜 별것두 아니지만 너무 궁금해서 성능을 확인해봤다.

위에꺼가 1부터 n까지 전체 계산했을때.

아래꺼가 1부터 n/2 까지 계산하고 n은 따로 더해줬을때.

 

우와 엄청 미세한 수치지만 진짜로 계산 시간이 절반정도 줄었다!!!

 

앞으로도 내가 미리 계산할 수 있는 건 컴퓨터한테 시키지 말고 내가 해주자!

 

 

 

---