[코딩테스트] 프로그래머스 숫자의 표현 파이썬(Python)

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

프로그래머스

이 문제를 수학적으로 푸신 분들이 있었지만 저는 이해하지 못해서 모든 경우의 수를 확인하면서 풀었습니다.

def solution(n):
    numbers = [i for i in range(1, (n // 2) + 2)]
    result = set()
    for i in range(len(numbers)+1):
        for j in range(i+1, len(numbers)+1):
            if sum(numbers[i:j]) == n:
                result.add(tuple(numbers[i:j]))
            elif sum(numbers[i:j]) > n:
                break
                
    if (n, ) not in result:
        return len(result) + 1
    
    return len(result)

- numbers : 모든 경우의 수를 확인하기 위한 숫자 리스트

예를들어 n이 15라면 1부터 8까지의 수가 저장되어 있습니다 -> [1,2,3,4,5,6,7,8]

15가 아닌 8까지 저장한 이유는 15를 만들기 위하여 사용한 숫자들 중에 15를 제외하고 8이상의 수

즉 (15 // 2) + 1이상의 수가 없기 때문에 8까지 저장하였습니다.

- result : 결과를 담을 집합자료구조입니다.

 

for i in range(len(numbers)+1):
        for j in range(i+1, len(numbers)+1):
            if sum(numbers[i:j]) == n:
                result.add(tuple(numbers[i:j]))
            elif sum(numbers[i:j]) > n:
                break

이중 반복문을 통하여 모든 경우의 수를 탐색합니다.

만약 연속된 리스트의 합이 n과 동일하다면

해당 리스트를 set에 add하기 위하여 tuple자료구조로 변환한뒤에 저장합니다.

 

리스트의 합이 n보다 커질경우에는 반복문 종료하여 시간을 줄이게 됩니다.

해당 코드를 작성함으로 효율성 테스트에 통과할 수 있었습니다.

 

if (n, ) not in result:
        return len(result) + 1

마지막으로 자기자신이 result에 없다면 자기자신을 추가해주고 결과를 반환해줍니다.