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

이번에 해결해 볼 문제는 프로그래머스에 있는 숫자의 표현이다.

---

문제 설명

• 자연수 n을 연속한 자연수들로 표현 하는 방법의 수를 구하면 된다.

문제 해결 아이디어

• 연속이라는 단어에 집중했다.

  • 연속하는 데이터를 처리할 수 있으면서 앞과 뒤로 삽입과 삭제가 자유로운 자료형을 생각해보면 Queue를 떠올릴 수 있다.
  • 따라서 Python의 deque를 사용해 Queue를 구현했다.

• 처음에는 반복적인 패턴이 존재 할 것이라 생각해 Dynamic Programming으로 해결해야 하는 문제가 아닌가 했지만 반복적인 패턴을 발견할 수 없어서 다른 방법으로 해결하였다.

문제 해결 코드

from collections import deque

def solution(n):
    answer = 1 # 자기 자신을 표현할 수 있는 방법 한 가지를 default로 한다.
    q = deque()

    for i in range(1, n+1):
        if sum(q) == n:
            answer += 1

        q.append(i)

        # Queue에 있는 자연수들의 합이 n보다 작아질 때까지 삭제
        # 삭제가 완료된 Queue는 Queue의 합이 n보다 작으므로 삽입 연산할 준비가 완료 되었다고 볼 수 있다.
        while sum(q) > n:
            q.popleft()

    return answer