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

문제 설명

이해하기는 쉬운 문제입니다. 연속된 자연수 k개로 n을 만들 수 있는 경우의 수를 구하는 문제입니다.

 

입출력 예는 위에서 확인 할 수 있습니다.

풀이

1번 풀이

def solution(n):
    answer = 0

    for i in range(1, n):

        arr = []
        for j in range(1, n + 1):
            arr.append(j)

            if len(arr) >= i:
                if sum(arr) == n:
                    answer += 1
                    break
                elif sum(arr) > n:
                    break

                del arr[0]

    return answer

변수 설명

answer: 전체 경우의 수를 계산합니다.

arr: 연속된 자연수를 담는 배열입니다.

간단 설명

가장 먼저 1 ~ n - 1 만큼 반복하는 부분은 연속된 자연수의 개수입니다. 1개로 만드는 경우 2개로 만드는 경우 ... n - 1개로 만드는 경우입니다. 사실 n - 1개로는 만들수 없어 비효율적입니다.

두번째 순회는 1 ~ n까지 순회하며 arr에 각 값을 담습니다. 만약 arr에 i 개 이상이 들어있다면 연속된 자연수의 합을 구합니다.

만약 합이 n과 같지 않다면 가장 먼저 들어온(작은 값)을 삭제합니다.

만약 합이 같다면 answer을 증가하고 break를 걸며 합이 크다면 break만을 겁니다.

 

쉽게 생각한 방법인 만큼 효율성이 그리 좋지 못했고 시간초과로 실패했습니다. 그리고 새로운 풀이를 시도했습니다.

2번 풀이

def solution(n):
    answer = 0

    for i in range(1, n):
        min_sum = 0
        for j in range(i):
            min_sum += j
        if min_sum > n:
            break

        center = n // i

        if center == i - 1:
            continue

        start = center - (i - 1) // 2
        end = center + (i - 1) // 2
        if i % 2 == 0:
            end += 1

        if i == 1 and start == n:
            answer += 1
        elif n == sum(range(start, end + 1)):
            answer += 1

    return answer

변수 설명

answer: 아까와 동일하게 전체 경우의 수를 담습니다.

min_sum: i개의 자연수를 최소한으로 담았을때 n보다 클 경우 전체 순회를 중지합니다. 예를 들어 5를 만들때 3개로 만든다면 1 + 2 + 3이 5 보다 이미 크기때문에 2 + 3 + 4나 1 + 2 + 3 + 4와 같은 모든 경우가 5보다 클 수 밖에 없습니다.

center: 연속된 자연수 i개를 통해 만들 경우 가장 중간의 값입니다.

start: 연속된 자연수 i개를 통해 만들 경우 시작 값입니다.

end: 연속된 자연수 i개를 통해 만들 경우 끝 값입니다.

간단 설명

위에서 설명한 min_sum을 통해 불필요한 외부 for문의 순회 횟수를 줄였습니다. 이로 인해 하나의 케이스를 빼고 모든 케이스를 통과했습니다.

하나의 케이스를 통과하기 위해 이중 loop를 제거해야겠다고 생각을 했고 규칙을 통해 계산하였습니다.

i개를 통해 n을 만들때 가장 중간에 있는 값을 구합니다(center). 이는 start와 end를 구하기 위함인데 i에서 2를 나눈값을 center의 앞, 뒤로 더해줍니다. (ex, 3개를 15를 통해 만들 경우 4, 6이 각 start, end가 됩니다). 이때 i가 짝수일 경우를 고려해 i - 1한 값에서 2를 나누어 줍니다. 홀수라면 i // 2와 (i - 1) // 2가 같지만 짝수는 다르기 때문에 만약 짝수라면 end에 하나의 값을 더해 줍니다.

그리고 start에서 end까지의 모든 수를 더한 값이 n과 같다면 answer을 증가시킵니다.

 

 

위 알고리즘을 이용하면 풀이-1 보다 훨씬 빠른 속도로 해결할 수 있습니다.