숫자의 표현(프로그래머스 - level2)

안녕하세요 강민성입니다.

블로그에 글을 올리는 게 처음이라서 두서가 없을 수도 있지만

최대한 이해하기 쉽도록 잘 올려보도록 하겠습니다.

우선 제가 현재 알고리즘을 공부하고 있는 사이트는 프로그래머스 라는 사이트입니다.

https://programmers.co.kr 이 주소로 들어가시면 알고리즘 문제 뿐만 아니라 좋은 강의들도 많으니

한 번 둘러 보시는 것도 좋을 것 같아요!

저는 파이썬으로 가능한 프로그래머스의 모든 문제를 다 풀 것이기 때문에 궁굼한 사항 있으면 다른 게시물을 참고하시거나 문의 주시면 감사하겠습니다 ㅎㅎ

문제 부터 설명을 드리면

[ 문제 ]

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 # 구하고자하는 값 answer을 0으로 초기화 
 
 
 
    for i in range(1, n + 1): # 어떤 자연수 부터 시작할지 결정하는 반복문
 
        sum = 0 #총합을 초기화, 초기화하는 위치가 중요하다.
 
        for j in range(i, n + 1): #i부터 시작해서 어디까지 더할지 결정하는 반복문
 
            sum = sum + j  #sum에 j값을 계속 더 해줘서 총합을 구해준다.
 
            if sum == n:  # 그 총합이 구하고자하는 n 값이 되면
 
                answer = answer + 1 #answer(연속 되는 자연수들도 몇 번 표현할 수 있는지)를 1올려주고
 
                break  #한 번 찾았으면 그 이 후에는 더 나올 수 없으므로 반복문을 깨준다.
 
            if sum > n:
 
                break #같은 원리로 수가 더 커져버리면 찾을 가능성이 없으므로 반복문을 깨준다.
 
 
 
    return answer

문제에 대한 제 풀이 입니다.

각각에 대한 자세한 설명은 주석을 통해 설명을 했습니다.

프로그래머스의 문제들은 생각보다 시간복잡도에서 막히는 문제들이 많은데 

이 문제 역시 처음에는 시간 복잡도에서 실패했습니다.

이를 해결한 코드는 21번째와 25번째의 break 입니다.

풀이방법에 따라 연속되는 자연수들을 더해가다가 

21번째 줄의 break는 연속된 자연수의 합이 원하는 값 n이 나오면 다음 수를 아무리 더해도 다시는 n이 나올 수 없으므로 break를 해주고

25번째 줄의 break는 연속된 자연수의 합이 원하는 값 n보다 커지면 다음 수를 아무리 더해도 다시는 n이 나올 수 없으므로 break를 해줍니다.

이 두 break를 통해 복잡도를 줄여 해결하였습니다.

다음으로는 다른 사람의 풀이입니다.

아무래도 알고리즘 이다 보니 풀이방법이 여러 개가 나오는데 저는 아직 파이썬이  미숙해서 그런지 파이써닉하게 풀지는 못하는 것 같습니다.

# 띠용하는 풀이
 
def expressions(num):
 
    return len([i  for i in range(1,num+1,2) if num % i is 0])

다음과 같이 한 줄로 간단하게 풀수도 있습니다.

코드에 대해서 설명을 드리자면

for i in range(1,num+1,2)

반복문을 돌리는데 1부터 num까지 홀수들만 반복해주고

if num % i is 0

이 때 num을 i로 나눴을 때 나누어 떨이지는 i들의 개수를 return합니다.

즉 n이 주어졌을 때 홀수인 약수의 개수를 구하는 건데 이렇게만 보면 왜 이게 연속된 자연수의 값인지 잘 이해가 안될 수도 있습니다.

예를 들어 생각해보도록 하겠습니다.

15를 예로 생각해보면

15의 홀수인 약수는 1,3,5,15가 있습니다.

1) 약수가 1

1로 인해 15는 연속하는 하나의 자연수, 15로 이루어져있음을 알 수 있습니다.

2) 약수가 3

3으로 인해 15는 5+5+5 의 합으로 표현되는 것을 알 수 있고 약간의 조작을 통해 4+5+6 이 되고 연속하는 자연수가 됩니다.

3) 약수가 5

5도 마찬가지로 3+3+3+3+3 즉, 1+2+3+4+5 로 표현이 가능합니다.

4) 약수가 15

15같은 경우는 위의 1) 2) 3) 과는 조금 예외적이다.  모든 홀수 2n+1는 n 과 n+1, 연속하는 두 수의 합으로 표현 할 수 있으므로

이 경우에는 7+8로 생각하면 될 듯 합니다.

마무리

단순하게 생각하면 별로 어려운 문제는 아니었지만 굉장히 효율적이게 약수의 개수만을 구해서 답을 얻을 수도 있었습니다.

문제를 풀면서 느낀 점은 문제를 단순히 코드로 구현하고 원하는 답을 도출해내는 것도 중요하지만

시간 복잡도를 고려해야하므로 처음 접근방식이 굉장히 중요하겠구나라는 걸 느꼈습니다.

지금까지 읽어주셔서 감사합니당.