밑의 링크는 프로그래머스에서의 문제 링크입니다.
코딩테스트 연습 - 숫자의 표현
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할
programmers.co.kr
주의해야 할 점
정확성뿐만 아니라 효율성도 테스트하는 문제입니다.
정확성만 테스트하는 문제라고 해도 어느정도 효율성에 맞는 코드를 짜야되지만,
이런 문제와 같이 효율성을 대놓고 체크하는 문제는 실행 시간이 빠른 코드를 짜는데도 집중해야 합니다.
저처럼 코드를 짜게 된다면 n을 연속한 자연수들로 표현하는 방법들을 구할 때
시작하는 수를 무작정 1부터 n까지 고려하면 더 비효율적인 코드가 나올 것입니다.
문제의 예제에서 시작하는 수는 n 그 자체인 15를 제외하면
1, 4, 7을 시작하는 수로 고려한 케이스가 15를 연속한 자연수들로 표현하는 방법이 나오는 케이스인데,
시작하는 수가 7보다 큰 8부터 15 바로 아래인 14까지는
절대로 연속한 자연수들로 15를 표현하는 방법이 나오지 않습니다.
이것만 잘 생각해서 코드를 짠다면 조금이라도 효율적인 코드가 나올 것입니다.
그리고 n 그 자체도 연속하는 자연수들로 표현하는 방법에 속한다는 것을 생각해야 합니다.
생각한 풀이 과정
- 시작하는 수를 1부터 어디까지 반복할 것인지를 저장하는 limit 변수를 선언합니다.
- 시작하는 수 1부터 limit까지 반복해봅니다.
- 시작하는 수부터 연속한 자연수들을 더해보면서 n과 비교해봅니다.
- 과정 3 중에 n보다 크게 된다면 다음 시작하는 수 케이스로 넘어갑니다.
- 과정 3 중에 n과 같다면 answer에 1을 더해주고 다음 시작하는 수 케이스로 넘어갑니다.
- 시작하는 수가 limit까지 모두 반복하고 나면 answer에 1을 더하고 반환합니다.
- 1을 더하는 이유는 15 = 15처럼 n 그 자체도 연속한 자연수들로 표현하는 방법으로 인정되기 때문입니다.
제출한 파이썬 코드
# 자연수 n이 매개변수로 주어집니다.
def solution(n):
# 연속된 자연수들로 n을 표현하는 방법의 수를 저장할 변수를 선언합니다.
answer = 0
# 연속한 자연수들 중에서 시작하는 수를 1부터 어디까지 셀 것인지를 저장하는 변수를 선언합니다.
# 예제의 n=15일 때, 시작하는 수는 1, 4, 7입니다.
# 시작하는 수는 n의 절반까지 생각하면 됩니다.
limit = n // 2 + 1
# 시작하는 수를 1부터 limit까지 반복해봅니다.
for start in range(1, limit):
# 연속한 자연수들의 합을 저장할 변수를 선언합니다.
# 시작하는 수인 start로 초기화합니다.
continue_sum = start
# 계속 반복해봅니다.
while True:
# 연속한 자연수들을 더해야하므로 start에 1을 더해 그 다음 숫자를 저장합니다.
start += 1
# continue_sum에 다음 숫자를 더해갑니다.
continue_sum += start
# continue_sum이 n보다 크다면
if continue_sum > n:
# 이번 케이스에서는 n을 연속한 자연수로 표현하지 못하므로 그냥 반복문을 탈출합니다.
break
# continue_sum이 n과 같다면
elif continue_sum == n:
# 이번 케이스에서는 n을 연속한 자연수로 표현할 수 있으므로 answer에 1을 더합니다.
answer += 1
# 반복문을 탈출합니다.
break
# 예제의 n=15일 때, 마지막 케이스인 15=15와 같이 그 수 자체도 연속한 자연수들로 표현하는 것이므로
# answer에 1을 더하고 반환합니다.
return answer + 1
제출 결과
느낀 점
문제를 풀면서 뭔가 더 효율적인 코드가 있을 것 같은데 다른 방법이 떠오르지 않았습니다.
문제에서 주어진 n의 조건이 10,000 이하의 자연수라서 통과할 수 있는 코드 같기도 합니다.
아직 다른 사람들의 풀이를 보지 못했는데 다른 방법으로는 어떻게 풀 수 있는지 좀 더 고민해보고 공부해봐야겠습니다.
댓글