숫자의 표현

 

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

프로그래머스

문제풀이

연속된 구간을 탐색하는 문제다. 투 포인터를 이용하면 효율적으로 풀이를 할 수 있다. 
제곱근을 이용한 등차수열의 합 공식을 이용하여 방법의 수를 계산하거나 이분탐색을 활용하여 풀이하게 되면 시간 복잡도를 더 줄일 수 있다.

def solution(n):
    answer = 0
    left, right, current_sum = 1, 1, 0
    while left <= n:
        # 합이 n보다 작으면 부분합을 키움
        if current_sum < n:
            current_sum += right
            right += 1
        # 합이 n보다 크면 부분합을 줄임
        elif current_sum > n:
            current_sum -= left
            left += 1
        # 합이 n과 같으면 카운트, 새로운 부분합의 시작 위치를 탐색
        else:
            answer += 1
            current_sum -= left
            left += 1

    return answer