[프로그래머스] Lv2. 숫자의 표현

문제

풀이

수학적인 풀이 방법이 있을 거 같았지만 도저히 생각이 나지 않아서 브루트포스로 풀었다. n이 10,000이하의 자연수이기 때문에 O(n^2)의 시간복잡도를 가진 풀이로 풀어도 시간초과는 발생하지 않는다

def solution(n):
    answer = 0
    start = 1
    
	# 1부터 시작해서 연속한 숫자들을 더해나가는 풀이
    while start <= n:
        sum = x = start
        while sum <= n:
        
        	# 더한 값이 n이 되면 answer 증가 후 break
            if sum == n:
                answer += 1
                break
            x += 1
            sum += x
        
        # 더하기가 시작되는 값 증가
        start += 1
    return answer

투포인터로 푸는 방식이 있다고 해서 이 블로그의 코드를 참고했다.

1. 차례대로 더하다가 sum이 n을 넘어서면 가장 앞의 값(start)을 빼준다
2. sum이 n보다 작다면 가장 큰 값(end)을 증가시켜 더한다
3. sum == n이 되면 가장 작은 값을 빼고 answer를 1 증가시킨다

이 풀이 방식은 배열의 전체를 한 번만 훑기 때문에 O(n)의 시간복잡도를 가질 수 있다.

def solution(n):
    answer = 0
    start = end = sumN = 1
    
    while end <= n:
        if sumN < n:
            end += 1
            sumN += end
        elif sumN >= n:
            if sumN == n:
                answer += 1
            sumN -= start
            start += 1
    return answer