숫자의 표현
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