[프로그래머스 Level 2] 숫자의 표현 (Python 파이썬) 풀이 방법

velog에서 마크다운 형식으로 작업하던 글을 tistory에서 다시 쓰게 되었다.

글을 쓰기 이전에 항상 서론을 적는 편이었는데, 앞으로 어떻게 할 지는 잘 모르겠다.

 

사실 아직 실력이 좋지 않아서, 기초를 다진답시고 Level1 문제를 막 풀곤 그랬는데 이제는 그럴 때가 아니라 판단했다. Level2 문제를 하나씩 풀면서 실력을 쌓아나가야 한다고 생각해서 정답률 높은 순으로 문제를 정복하려 한다.

 

 

프로그래머스 <숫자의 표현> 문제 보기

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

 

프로그래머스 <숫자의 표현> 문제 풀이

def solution(n):
    answer = 0
    check = 0
    for i in range(1, int(n/2)+1):
        check = 0
        for j in range(i, n+1):
            check+=j
            if check == n:
                answer += 1
                break
            elif check > n:
                break
    return answer+1

사실 바로 통과하지는 못했다.

 

 

 

첫 번째 도전

def solution(n):
    answer = 0
    check = 0
    for i in range(1, n+1):
        check = 0
        for j in range(i, n+1):
            check+=j
            if check == n:
                answer += 1
                break
    return answer+1

완전탐색의 방식으로 i를 1부터 n까지 순서를 정해주며 이중 반복문 안에서 j로 check에 값을 더해 연속적인 수의 합이 n과 같은 경우가 있는지 answer에 수를 더해주었다. n이 10,000 이하의 자연수니까 이중 반복문은 효율성 테스트에서 걸릴거같은데 ... 라는 생각으로 도전했지만 역시나 실패

 

 

두 번째 도전

def solution(n):
    answer = 0
    check = 0
    for i in range(1, int(n/2)+1):
        check = 0
        for j in range(i, n+1):
            check+=j
            if check == n:
                answer += 1
                break
    return answer+1

n을 2로 나눈 값을 초과하는 수들에서는 연속적인 합이 나올 수 없다는 효율성 힌트를 얻고서 반복문의 범위를 반으로 줄였지만 역시나 예상대로 효율성 테스트는 통과하지 못했다.

 

 

세 번째 도전

def solution(n):
    answer = 0
    check = 0
    for i in range(1, int(n/2)+1):
        check = 0
        for j in range(i, n+1):
            check+=j
            if check == n:
                answer += 1
                break
            elif check > n:
                break
    return answer+1

check가 n보다 커질 경우에는 더 이상 반복문을 돌 필요가 없다느 것을 깨닫고 elif문을 추가해주었다.

 

 

그랬더니 통과! 하지만 7점을 받으면서도 기분이 좋지 않았던 이유는, 내가 봐도 내 코드가 좋아보이지 않았기 때문. 분명 더 좋은 풀이가 있을 것이라 생각했다. 실제로, 수학적인 풀이를 찾아볼 수 있었다.

 

 

 

다른 풀이

def solution(n):
    answer = 0
    temp = n
    i = 1
    
    while(temp > 0):
        if(temp%i == 0):
            answer += 1
        temp -= i
        i += 1
        
    return answer

효율성 테스트 속도가 말도 안 되게 빨라졌다!

 

while문을 도는 temp에 i를 빼가며 나눠지는 수가 있는 경우에는 i에 따라 앞뒤로 연속적인 수가 분명히 있다는 가정이 생기므로 해당 풀이가 가능해지는 것이다. 아래에서 자세히 예시를 살펴보도록 하자.

 

example

temp=15라고 하면,

 

15 % 1 == 0 ( 이 경우의 연속적인 경우: 15 )

(15-1) % 2 == 0 ( 이 경우의 연속적인 경우: 7 8 )

(15-1-2) % 3 == 0 ( 이 경우의 연속적인 경우: 4 5 6 = 4 (4+1) (4+2) )

(15-1-2-3) % 4 != 0

(15-1-2-3-4) % 5 == 0 ( 이 경우의 연속적인 경우: 1 2 3 4 5 = 1 (1+1) (1+2) (1+3) (1+4) )

 

위처럼 총 4가지의 경우가 나오게 되는 것이다.

 

 

조금 솔직해지자면, 수학적 풀이에 강하다고 생각했는데 자만하지 않아야겠다고 느꼈다. 세상에는 똑똑한 사람들이 참 많다. 나는 우물 안의 개구리🐸