-
코딩테스트 연습> 연습문제> 숫자의 표현ALGORITHM/Programmers 2020. 7. 15. 01:24728x90
<문제링크: https://programmers.co.kr/learn/courses/30/lessons/12924>
문제설명: 숫자 n이 주어지고 1부터 n까지의 연속된 숫자를 활용하여, 합이 n이 되는 경우의 수를 찾는 문제이다.
[1차 시도]
def solution(n): cnt=0 cur=1 while cur != n+1: temp=0 for i in range(cur,n+1): if temp+i<=n: temp+=i if temp==n: cnt+=1 break else: break cur+=1 return cnt
풀이: 합이 n이 될 때 개수를 세어 줄 cnt 변수와 1부터 시작해 차례로 새롭게 더해줄 변수 cur를 만들어준다.
while 문을 돌면서 현재 위치의 숫자, 즉 첫 번째 기준이 되어 더해 온 숫자가 n이 될 때 까지 반복한다.
만약 n이 10이라면,
1+2+3+4 = 10 (cur=1)
2+3+4+5 >10 (cur=2)
3+4+5 > 10 (cur=3)
4+5+6 > 10 (cur=4)
...
10 = 10 (cur=10)
반복하면서 합이 n이 되는 것을 찾아야하기 때문에 temp를 0으로 초기화 시키고, 아래 for문을 돌면서 현재 숫자부터 n까지의 원소 중 n을 넘지 않는 선에서 차례로 연속적인 숫자들을 더해준다. 이 때 누적합 temp가 n과 같다면 정답인 cnt에 1을 더해주고 for문을 종료한다.
또한 합을 누적하면서 n을 넘어간다면 바로 종료하고 경우의 수에는 합하지 않는다. for문이 종료되면 cur를 1 증가시켜 새로운 시작점의 기준을 갱신해주고 마지막으로 cnt를 return한다.
채첨결과: 정확성과 효율성 테스트 모두 잘 통과하지만 시간을 더 줄일 수 있는 다른 방법을 적용해봤다.
[2차 시도]
def solution(n): cnt=0 cur=1 while cur != n: temp=0 for i in range(cur,n//2+2): if temp+i<=n: temp+=i if temp==n: cnt+=1 break else: break cur+=1 return cnt+1
풀이: for문의 range를 굳이 n까지 돌릴 필요는 없었다. 어차피 숫자 n의 절반 이상 넘어가는 숫자를 기준점으로 잡으면 그보다 큰 숫자를 더하는 것은 의미가 없으므로 for문의 범위를 n의 절반+2까지로 설정해서 n의 절반+1 숫자까지 보면된다.
n이 15일 때 n//2는 7이고,
cur가 7일 때 7+8=15이고
cur가 8일 때 8+9>15가 되므로,
n//2+2까지만 보면 실행시간을 어느정도 줄일 수 있다.
사실 절반으로 줄일 수 있다고 생각했지만, 어차피 누적합이 n을 넘어가면 break로 종료되므로, 실행시간이 현저히 줄어 들지 않는 것 같다.
그리고 마지막에 숫자 n자신을 cnt에 포함시켜 return 해주면 된다.
채첨결과: 효율성 테스트의 시간을 조금이나 더 줄여볼 수 있었다.
'ALGORITHM > Programmers' 카테고리의 다른 글
코딩테스트 연습> 탐욕법(Greedy)> 큰 수 만들기 (0) 2020.07.22 코딩테스트 연습> 스택/큐> 다리를 지나는 트럭 (0) 2020.07.18 코딩테스트 연습> 연습문제> 피보나치 수 (0) 2020.07.13 코딩테스트 연습> 연습문제> 올바른 괄호 (0) 2020.07.12 코딩테스트 연습> 힙(Heap)> 더 맵게 (0) 2020.07.03