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

시험 준비를 조금 하느라 포스팅을 오랜만에 하게 되었다.

추석 연휴까지는 포스팅을 많이는 못할 것 같다 ㅠㅠ

 

그럼 이번 문제를 보자.

프로그래머스 숫자의 표현을 파이썬으로 풀어보겠다.

레벨은 2로 되어있지만 예전 문제라 쉬운 편이다.

 

---

문제

 

---

구현

 

구현은 매번 sum을 하면 시간이 오래 걸리기 때문에

숫자를 하나씩 더하고 빼면서 sum을 저장하는 방식

이미지화하면 윈도우를 슬라이딩하는 방식(?)으로 구현해보겠다.

 

설명이 좀 모호해서 코드로 보겠다.

---

코드

 

def solution(n):
    answer = []
    suma, count=0, 0
    i=1
    while i<n:
        if suma <= n:
            answer.append(i)
            suma+=i
            i+=1
        else:
            suma-=answer[0]
            del answer[0]

        if suma == n:
            count+=1

    return count+1

 

우선 반복문을 돌며

만족하는 값보다 커지기 전까지

answer 리스트와 suma에 값을 추가하고 더해준다.

만약에 더 커지면 suma와 answer 리스트에서 빼준다.

 

그 후 suma값과 n이 같으면 count를 해준다.

 

이렇게 count를 해주고 마지막의 n은 바로 더해준다.

ex) 15 = 15 

 

예전 문제라 그런지 그렇게 어렵지 않게 풀 수 있다.

---

다른 풀이

이 방법은 이해하는데 오래 걸렸다.

결국 프로그래밍의 최적화는 수학인 걸 보여주는 코드이다...

def expressions(num):
    return len([i  for i in range(1,num+1,2) if num % i is 0])

 

이해를 위해 등차수열의 합 공식에 첫 항 a, 공차 1, 마지막항 k를 대입하면 아래와 같다.

k(2a + k -1)/2 == n으로 둘 수 있다.

 

이를 a로 정리하면

a = n/k + (1-k)/2 다

결국 a가 자연수가 되려면 n/k가 자연수, 1-k/2가 정수가 되어야 하므로

k는 n의 약수, k는 홀수가 되어야 한다.

즉 k는 홀수이고 n의 약수여야 한다.

 

이렇게 되면 위의 코드가 나온다.

 

솔직히 테스트에서 바로 풀라고 하면 이런 생각을 하지 못할 것 같지만

참고를 위해 한번 정리해봤다.