[프로그래머스][Java] Lv.2 숫자의 표현

문제설명

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 이하의 자연수이다.

---

풀이과정 1) 단순 반복문

1. 1부터 n까지 모든 수를 더하면서 n과 같아지면 answer값을 늘리고 반복문을 빠져나온다.
   -> n과 같지 않고 연속적으로 더했을 때 sum이 n보다 커지는 경우는 더이상 조사할 필요 없이 반복문만 빠져나온다.
2. 2부터 n까지 쭉 더하면서 n과 같아지는 지점을 찾고 다음 반복문으로 넘어감.
3. 시작하는 숫자를 1부터 n까지 위의 과정을 반복한다.

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        //1부터 n까지 연속으로 더하다가 n과 같거나 크면 다음 반복
        //2부터 n까지 연속으로... 이런식으로 계산함.
        for(int i=1;i<=n;i++){
            int sum=0;
            for(int j=i;j<=n;j++){
                sum+=j;
                
                if(sum==n){ //연속된 숫자의 합이 n일 때
                    answer++;
                    break;
                }
                if(sum>n) break;
            }
        }
        return answer;
    }
}

 

단순 반복문으로 풀이과정을 도출해내기 쉽지만, 시간복잡도가 O(n^2)이라는 점이 조금 아쉽다.

 

---

풀이과정 2) 규칙성 찾기

이 방법을 처음에 사용하다가 타임어택 시간이 끝나버려서 마무리 하지 못했지만,

이렇게 푼 분이 계셔서 해당 풀이를 참고하여 마무리할 수 있었다.

 

 

일단 경우를 두가지로 나누어 문제 풀이를 정리하였다.

 

1. n을 홀수 개의 연속된 숫자로 표현할 수 있는 경우

- 1개 : n = n

- 3개 : n = (a-1)+a+(a+1) = 3*a ====> n이 3으로 나누어 떨어지면 n은 연속된 세개의 수의 합으로 표현할 수 있다는 것.

- 5개 : n = (a-2)+(a-1)+a+(a+1)+(a+2) = 5*a

- (2b-1)개 : n = b-(a-1)+...+a+...+b+(a-1) = (2b-1)*a

 

따라서 반복되는 숫자의 개수가 i라면 n이 i의 배수 일 때, n은 i개의 연속된 수로 표현할 수 있다는 것을 확인할 수 있습니다.

 

 

2. n을 짝수 개의 연속된 숫자로 표현할 수 있는 경우

- 2개 : n = (c-1)+c    ===> n이 홀수라면 무조건 연속된 숫자 2개로 표현할 수 있다.

- 4개 : n = (c-2)+(c-1)+c+(c+1) = 2*(2c-1)

- 6개 : n = (c-3)+(c-2)+(c-1)+c+(c+1)+(c+2) = 3*(2c-1)

- 2d개 : n = (d-c)+...+c+...+(d+c-1) = d*(2c-1) (*주의: d-c는 자연수여야함.)

따라서 반복되는 숫자가 2d개 일 때, n/d가 홀수이고 연속된 첫번째 숫자가 0보다 크면 2d개의 연속된 수로 표현될 수 있음을 알 수 있다.

[설명을 너무 못하죠.. 죄송해요..]

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1;i<=n;i++){
            //i가 짝수일 때
            if(i%2==1){
                if(n%i==0){
                    answer++;
                }
            }
            //i가 홀수 일때
            else{
                int c = n/2;
                int d = i/2;
                
                if(d-c>0 && n/d%2==1)
                    answer++;
            }
        }
        return answer;
    }
}

 

진짜 풀이과정 백지에 적으면서 될 것같으면서 안되서 짜증났는데, 풀이를 찾았더니 편-안해졌다. 앞으로 갈 길이 멀구만..

 

이 풀이과정은 점화식까지 써봐야지만 도출해낼 수 있을 것 같아서 힘들지만,

복잡도는 O(n)까지 줄어들어 결과가 만족스럽다.   효율성 테스트 결과를 보면 확실히 알 수 있다.