프로그래머스 숫자의 표현

숫자의 표현 : programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현

숫자 n이 주어질때 연속한 자릿수의 수들을 더하여 n을 표현하는 방법의 가짓수를 구하는 문제였다.

이 문제는 답이 0이 나올수 없기 때문에 answer에 1을 박고 시작하였다.(n은 단순 n으로표현 할 수 있기때문)

이후 for문을 돌아주는데 n까지 다도는게 아니라 중간까지만 돌아준다.(n/2)+(n/2+1)는 n을 넘어가기 때문이다.

그렇게 n이 나오면 answer를 증가 시키는 방법으로 풀었다.

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 1;

        for (int i = 1; i <= n / 2; i++) {
            if (isPossible(i, n)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean isPossible(int start, int limit) {

        int num = 0;
        while (true) {
            num += start++;
            if (num == limit) {
                return true;
            } else if (num > limit) {
                return false;
            }
        }
    }
}

근데 더쉽게 푸는 방법이있다.

이거는 수학적으로 푸는 건데 특정수를 연속한 자릿수의 수들을 더하여 표현하는 방법의 가짓수는 자신의 약수들중 홀수의 갯수로 표현 할수 있다.

예를 들어

15에는 1, 3, 5, 15의 홀수 약수가 존재한다.

역시 15는 15, 7+8, 4+5+6, 1+2+3+4+5이렇게 네가지 방법으로 구할 수 있다

public static int solution(int n) {
		int answer = 0;

		for (int i = 1; i <= n; i += 2) {
			if (n % i == 0) {
				answer++;
			}
		}
		return answer;
	}

이는 코드도 훨씬간결할 뿐더러 더 빠르다.