[프로그래머스] 숫자의 표현(python)

프로그래머스, 숫자의 표현

TL;DR

• 투 포인터(two pointer)를 활용하여 문제를 해결할 수 있는지

문제 분석

1. 자연수 n을 연속한 자연수로 표현하는 방법이 여러 개가 존재한다.
2. 자연수 n이 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return 하는 함수를 완성하라.
3. n <= 10,000 자연수

 

입출력 형태

입출력 예시

- n이 15로 주어졌을 때의 출력은 4가 된다.

풀이

def solution(n):
    answer = 0
    
    for i in range(1, n + 1):
        _sum = 0
        for j in range(i, n + 1):
            _sum += j
            if _sum == n:
                answer += 1
                break
            
            if _sum > n:
                break
                
    return answer

 

- 이전에 리트코드에서 푼 투 포인터 문제들은 양 끝단, 즉, 배열의 시작과 끝을 left와 right라는 변수를 할당하고 푸는 문제들이었다.

- 이번 문제도 마찬가지로 투 포인터라고 분류 할 수 있기 때문에 두 개의 시작과 끝을 나타내는 변수인 left와 right를 사용하려고 하였다.

- 하지만, 그럴 경우 시간 초과로 인해 문제를 해결할 수가 없다. 불필요하게 많은 경우를 살펴보게 되기 때문이다.

- 투 포인터는 꼭 양 끝단의 인덱스를 사용하여 문제를 푸는 방법을 말하지는 않는다. 그저, 배열에서 두 개의 인덱스 변수를 사용하여 문제를 해결하는 것을 의미하는 것이었다.

- 문제의 풀이는 간단하다. 1부터 n까지의 수를 순회하며, i는 시작지점을 j는 시작지점으로부터 증가시키며 합을 비교하면 된다.

- 합이 n이 될 경우는 정답에 1을 추가하고, 반복문을 종료, 시작 지점에 1을 더한다.

- n보다 클 경우는, 더 이상 정답이 나올 수 없는 경우이므로 반복문을 종료한다.