소소한 컴퓨터 이야기

숫자의 표현

by Cori

문제

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

 

· 1 + 2 + 3 + 4 + 5 = 15 

· 4 + 5 + 6 = 15 

· 7 + 8 = 15

· 15 

 

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

제한사항

· n은 10,000이하의 자연수입니다.

 

입출력 예

n result
15 4

풀이

1. Me

1) 1차 시도

def solution(n):
    list_n = list(range(1,n+1))
    # print(list_n)
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i
        for j in range(i+1, len(list_n)):
            if sum(range(list_n[i], list_n[j])) == n:
                # print(i, j)
                answer += 1
    # print(answer)
    return answer

연속된 수를 구하기 위해, 입력받은 수에 해당하는 범위까지의 수를 담은 리스트를 만들고, 해당 리스트를 이중 탐색하며 두 개의 인덱스를 통해 연속된 수의 덧셈을 구현하였다.. 정확성 테스트는 모두 통과하였지만, 효율성에서 다 틀렸다.. 주륵 ..

 

2) 2차 시도

def solution(n):
    list_n = list(range(1, (n+1) // 2 + 1))
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i   # 0 ~ 7
        for j in range(i+1, len(list_n)):   # 1 ~ 7
            if sum(range(list_n[i], list_n[j] + 1)) == n:
                answer += 1
    return answer

길이를 절반으로 줄여도 여전히 효율성 테스트에서 통과하지 못한다 ..

 

3) 3차 시도

def solution(n):
    list_n = list(range(1, (n+1) // 2 + 1))
    print(list_n)
    answer = 1   # 자기 자신 
    for i in range(len(list_n)):
        start_idx = i   # 0 ~ 7
        for j in range(i+1, len(list_n)):   # 1 ~ 7
            if sum(range(list_n[i], list_n[j] + 1)) == n:
                # print(i, j)
                answer += 1
                break
            elif sum(range(list_n[i], list_n[j] + 1)) > n:
                break
    # print(answer)
    return answer

길이를 절반으로 줄이고, break문을 사용하여 최소한으로 반복하도록 구현하였다.. 그랬더니 통과 ! 

 

2. Others

def expressions(num):
    answer = 0
    for i in range(1, num + 1):
        s = 0
        while s < num:
            s += i
            i += 1
        if s == num:
            answer += 1

    return answer

이렇게 작성하면 한 번만 탐색하고 마무리 할 수 있는건가 .. ? 시간복잡도가 어떻게 되는거지 잘 모르겠다.

def expressions(num):
    return len([i  for i in range(1,num+1,2) if num % i is 0])

등차수열 합의 공식을 이용했다고 한다.. 자기보다 작은 홀수로 나누어 떨어지는 값의 개수 = 문제의 답 

 

'CS > Coding Test' 카테고리의 다른 글

올바른 괄호  (0) 2021.09.04
다음 큰 숫자  (0) 2021.09.03
문자열을 정수로 바꾸기  (0) 2021.09.03
문자열 내 마음대로 정렬하기  (0) 2021.09.03
문자열 내림차순으로 배치하기  (0) 2021.09.03

블로그의 정보

코딩하는 오리

Cori

활동하기