숫자의 표현
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12924
문제에 대한 내용
문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7 + 8 = 15
- 15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한 조건
- n은 10,000 이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 15 | 4 |
입출력 예 설명
입출력 예#1 문제의 예시와 같습니다.
접근 방식
- 각 숫자에서 연속된 숫자를 계속 더 한다.
- 만약 주어진 숫자를 넘어가면 종료
- 주어진 숫자와 일치하면 answer + 1
잘못된 접근
테스트 케이스가 모두 통과되어서, 제출을 했더니 효율성 테스트에 걸렸다.
class Solution {
public int solution(int n) {
int answer = 0;
int tmp[] = new int[n+1];
for(int i=1; i<=n; i++) tmp[i] = i;
for (int i=1; i<=n; i++){
A: for (int j=i+1; j<=n+1; j++){
if (tmp[i]+j <= n) tmp[i] += j;
if (tmp[i] == n){
answer++;
break A;
}
}
}
return answer;
}
}
최대한 효율을 높일 수 있도록 코드를 변경해야 한다.
그래서 코드 라인마다 필요성과 효율성에 대해 따져보며 코드를 수정했다.
- tmp 배열이 필요한가? => X
- 2중 for문이 필요한가? => O
- 두 번째 for문에서 합이 n을 이미 벗어났더라도 지속되는 for문
위 내용을 바탕으로 로직을 수정했다.
결과
소스 코드
class Solution {
public int solution(int n) {
int answer = 0;
int sum = 0;
for (int i=1; i<=n; i++){
sum = 0;
for (int j=i; sum<=n; j++){
sum += j;
answer = sum==n ? answer+1 : answer;
}
}
return answer;
}
}
- 먼저 tmp 배열을 제거했다. (어차피 해당 숫자부터 시작이 되기에)
- 이후에, 숫자의 합은 sum이라는 변수를 통해 관리했다. 두 번째 for문 진입 전, 0으로 초기화
- 두 번째 for문의 조건을 변경
- sum이 n보다 작거나 크도록 하여 벗어나면 for문이 더 이상 진행되지 않는다.
- 삼항연산자를 통해 n과 같으면 +1
결과 이미지
다른 접근 방식
대부분 비슷한 방식의 풀이였다.
그 중에, 수학적 지식이 필요한 코드가 있었다.
class Solution {
public int solution(int n) {
int answer = 0;
for (int i = 1; i <= n; i += 2) {
if (n % i == 0) answer++;
}
return answer;
}
}
바로 이 코드인데, 정수론 정리를 이용한 풀이다.
정수론 정리란? 주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는, 주어진 수의 홀수의 개수와 같다고 한다.
따라서 주어진 숫자의 홀수의 수를 구하면 끝이다. 실제로 테스트 결과를 확인해 보니, 비교도 안 될정도로 훨씬 빠른 속도가 나왔다. (당연히 for문이 한 개이니..)
알게 된 점
정수론 정리에 대해 알게 되었다.