먹고 기도하고 코딩하라

[Python3] 프로그래머스 lv.2 12924 숫자의 표현 본문

자료구조&알고리즘/프로그래머스

[Python3] 프로그래머스 lv.2 12924 숫자의 표현

2G Dev 2022. 7. 1. 09:51
728x90
728x90

 

문제 설명

 

코딩테스트 연습 - 숫자의 표현

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

programmers.co.kr

 

완전탐색으로 풀 수 있는 문제다.

나는 이것을 호기롭게 투포인터로 풀려고 했지만.. 효율성에서 전부 시간 초과로 실패했다.

# 시간 초과
def solution(n):
    mid = (n // 2) + 1
    cnt = 1
    for i in range(1, mid+1):
        l, r = i, mid
        while l < r:
            target = sum(range(l, r+1))
            if target == n:
                cnt += 1
                break
            if target > n:
                r -= 1
            else:
                break
    return cnt

 

렙2 문제인데 너무 어렵게 생각할 거 없었고, 그냥 2중 루프문 만들면 됐었다(...)

쉽게 생각하니까 그냥 허무하게 잘 풀린다.

위 코드가 시간 초과를 당한 건 아마 sum 함수 때문인 것 같다. 예전에도 같은 실수로 시간 초과를 당한 적이 있다.

 

일단, 문제 예시에서 주어진 15의 경우처럼 어떤 수를 이루는 연속된 숫자가 2개 이상이 되면 n//2 + 1까지만 검사하면 된다. (사실 큰 의미는 없으나, 그냥 n으로 할 때보다 범위가 줄어드는 효과가 있다)

자기 자신은 그냥 더하면 되니까 cnt는 1로 초기화한다.

2중 루프를 돌리면서 쭉쭉 더해나가다가 n이 되면 cnt를 추가하고,

n이 넘어버리면 더 이상 가망이 없으니 루프를 다시 돈다.

def solution(n):
    mid = (n // 2) + 1
    cnt = 1
    for i in range(1, mid):
        val = 0
        for j in range(i, mid+1):
            val += j
            if val == n:
                cnt += 1
                break
            if val > n:
                break
    return cnt

 

728x90
반응형
0 Comments
댓글쓰기 폼