[programmers] 숫자의 표현

프로그래머스 Lv.2 숫자의 표현

포스팅에 문제 해석도 같이 적으면 좋을 것 같아서, 이번 문제부터는 그렇게 작성하기로 하였다.

문제 해석

자연수 n을 연속한 자연수로 표현하는 방법의 갯수를 구하는 문제이다.

ex) 15 = 15
	15 = 7 + 8
    15 = 4 + 5 + 6
    15 = 1 + 2 + 3 + 4 + 5
    따라서 f(15) = 4 가 된다.

작성한 코드

def solution(n):
    import math
    answer = 1  # 자기자신은 반드시 가능한 케이스이므로, 초기값을 1로 설정한다.
    num = 1     # 탐색을 시작할 숫자
    count = 0
    while num < math.ceil(n/2):  # 이렇게 하는 이유는, 절반의 값을 넘으면 절대 불가능하기 때문.
        count = 0
        for i in range(num,n):
            if count + i < n:
                count += i
            else:
                if count + i > n:
                    num += 1
                    break
                elif count + i == n:
                    answer += 1
                    num += 1
                    break
    return answer

메인 아이디어

1. 숫자 num 부터 연속되는 숫자의 합을 구하되
2. 다음 숫자와의 합이 n보다 작으면 계속해서 더하고,
3. 다음 숫자와의 합이 n을 넘어서면 => 5번
4. 다음 숫자와의 합이 n과 같으면 answer에 1을 더해준 후 => 5번
5. num+1에 대해 1~4과정을 반복한다.
6. 다만 num이 n의 절반을 넘어간다면 확인할 필요가 없다.
	(=> n/2 + 1 + n/2 = n+1 로, 반드시 n을 넘어서기 때문.)
7. 또한, 자기 자신은 반드시 가능하기 때문에 answer은 1부터 시작한다.
	(즉, n/2부터 n사이의 숫자는 확인 할 필요가 없다!)

즉 num의 숫자를 증가시키는 반복문과,
num부터 시작하여 연속된 숫자를 더하는 반복문이 모두 필요하다.

자체 리뷰

1. 더 효율적으로 계산하는 방법이 있을까?

다른 사람의 코드

def expressions(num):
    return len([i  for i in range(1,num+1,2) if num % i is 0])

이 방식은 제시된 문제와 동치 관계인 수학적 지식을 이용한 풀이이다.

생각 정리

1. 효율성 측면에서 내 풀이와 비교하면 어떤 것이 얼마나 더 좋을까?
2. 코드에 대한 효율성을 측정할 줄 알아야 할까?
   이게 O(n) 인지.. O(n**.5)인지.. 직관적으로 알아야 하려나?