프로그래머스 Lv2 - 숫자의 표현 - JAVA

안녕하세요 놀이방사장입니다.

 

이번 포스팅은 프로그래머스Lv2

"숫자의 표현" 입니다.

 

자연수 n을 만들수 있는 연속된 자연수 표현 방법의 갯수를 찾아내면 됩니다.

 

여기서 문제를 풀 수 있는 방법이 2개가 있습니다.

 

하나는 그냥 for문을 이용해서 하나씩 직접 만들어 보는 방법입니다.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=1; i< n+1; i++){
            int sum = 0;
            int count = 0;
            while(sum <=n){
                sum = sum+i+count;
                count++;
                if(sum == n){
                    answer++;
                }
            }
        }
        return answer;
    }
}

1부터 하나씩 비교해주는 방법입니다.

 

2번쨰 방법은 수학적으로 접근하는 방법입니다.

이론은 주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 약수 갯수 중 홀수인 약수의 갯수와 같다라는 정수론이 있다.

이걸 그대로 구현해주면 된다.

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

    public int solution(int n) {
        int answer = 0;
        answer = Finn(n);
        return answer;
    }
}

이렇게 구현하면 속도가 0.7ms나오는데 위에껄로하면 0.5ms로 더 빠르다.

 

근데 사실 밑에 코드는 함수를 계속 호출하기 때문에 더 느린 듯

 

느낌이지만 그냥 solution함수안에 그대로 넣으면 속도는 비슷할듯!

 

이상으로 포스팅 마치겠습니다.!