[Python] 프로그래머스(Lv2) - 숫자의 표현

안녕하세요 :)

https://programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스 숫자의 표현 문제입니다.

아래 예시 그림처럼 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 문제입니다.

제한사항

• n은 10,000 이하의 자연수 입니다.

n이 10,000 이하의 자연수기이기 때문에 for문을 한번만 돌아야 합니다 !
두 번 돌아서 시간복잡도 O(n^2) 이 된다면 시간초과가 납니다.

** 정답 O(n)

def solution(n):
    answer = 0
    
    if n % 2 == 0:
        while n % 2 != 1:
            n //= 2
    
    divisor = 0
    for i in range(1, n//2+2):
        if n % i == 0:
            divisor += 1  
            
    return divisor + 1

==========================================
처음에 O(n^2)으로 푼 코드입니다.
** 시간초과 O(n^2)

def solution(n):
    answer = 0
    
    for i in range(1, n//2+2):
        now_sum = i
        for k in range(i+1, n//2+2):
            now_sum += k
            if now_sum == n:
                answer += 1
                break
        
    return answer + 1