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

문제 설명

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 이하의 자연수 입니다.

입/출력

---

풀이

def solution(n):
    answer = 0
    cnt = 0
    for i in range(1,n): #0은 제외하고 시작.
        sum = i # for문이 초기화 될 때마다 새로 시작되는 i의 값을 받음
        for j in range(i+1,n):
            sum += j #i+1한 값부터 j를 시작해 n까지 더함
            if sum == n: # 만약 더한 값이 n값과 같아 진다면 경우의 수 answer + 1
                answer += 1
                break
            elif sum>n: #더한 값이 n보다 커졌다면 반복문에서 벗어남.
                break
    return answer+1 #자기 자신 값까지 포함해야 하기 때문에 +1

결과

---

느낀 점

등차수열의 합 공식을 알면 더욱 쉽게 풀 수 있는 문제였다. 수학은 기본지식 밖에 안 가지고 있는 나로서는 생각지도 못한 풀이였다.

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

효율성에서 많은 시간을 줄일 수 있다.

이 풀이를 사용해서 문제를 해결한다면 시간 복잡도에서도 많은 시간을 줄일 수 있었다. 입력받은 값까지 1부터 n까지의 홀수를 n에 나눈 수가 나머지가 0인 개수가 답이라는 것이다. 역시 머리 좋은 사람들은 대단하다.

 

요즘 그래도 알고리즘 실력이 예전보다는 늘었다고 생각했는데.. 한참 부족한 것 같다. 당장 2020년도 얼마 남지 않았고 2021년 상반기에는 꼭 내가 원하는 기업이 아니더라도 커리어로서 부족함이 없는 회사에 가고 싶다. 더 노력하자.