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

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

---

제한사항

• n은 10,000 이하의 자연수 입니다.

---

입출력 예

n	result
15	4

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

---

from collections import deque

def solution(n):
    answer = 1 #자기자신
    
    nums = deque()
    nums_sum = 0
    for i in range(1, n):
        while nums_sum + i > n: #(큐 총합 + i)가 n 이하가 될 때까지 popleft
            last = nums.popleft()
            nums_sum -= last
        nums.append(i)
        nums_sum += i
        
        if nums_sum == n: #총합이 n이 되었을 때 answer += 1
            answer += 1
                        
    return answer

 

어제 오늘 거 미리 풀려고... 구명보트인가 풀어보려다가 효율성에서 막혀서 울먹이다가

오늘 18분만에 푼 숫자의 표현....

큐 사용했더니 호다닥 풀 수 있었다

 

1) 큐에 i를 넣었을 때 총합이 n 이하가 될 때까지 작은 값들을 popleft 하고

2) 그 후 i를 넣어주고

3) 만약에 그 값이 n과 같다면 answer += 1를 해준다

 

3번에서 popleft를 해주려고 했는데, 어짜피 그 이후 while을 돌면서 빼주니까 상관없어서 지웠다 ㅎ

 

알고리즘 공부를 조금씩 하다보니까 (그래봤자 다 합치면 약 1-2달만 공부한 거지만)

어떤 문제를 봤을 때 이건 큐로 풀어야지, 이건 이렇게 풀어야지 하는 길이 보이는 것이 신기하다

점점 재미 붙어가는 중...!!!

잘하지 못해서 재미가 없었던 거니까 잘하게 되면 더 재밌어지겠지