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

문제

 

풀이

 

연속된 숫자의 합이 n이 되는 모든 경우의 수를 구하는 문제다.

처음에 연속된 숫자의 합이니까 등차수열로 풀어야겠다.. 라고 생각하고 문제를 접근했다.

첫 번째 풀이

n: 주어진 수(합한 값), a: 첫째항, b: 마지막항

기본 베이스는 위의 등차수열 공식을 생각하고 문제를 풀었다.

1. n==n인 경우를 미리 세어주기 위해 count를 1로 초기화함

2. 이중 for문으로 저 공식을 만족하는 a, b 값이 존재하면 count를 늘려줌

3. for문 다 돌면 count 반환

이렇게해서 테스트 케이스는 다 통과됐는데... 시간복잡도 O(n^2)이라 그런지 시간초과가 뜸 ㅜㅜ 다른 방법으로 풀면 되는데 오기가 생겨서 등차수열 고집하다가 시간 많이 버린 문제...ㅋㅋ 

class Solution {
    public int solution(int n) {
        int count = 1;
        for(int a=1; a<n+1; a++){
            for (int b=a+1; b<n+1; b++){
                if ((b-a+1)*(b+a)/2 == n) count++;
            }
        }
        return count;
    }
}

 

두번째 풀이

 

그래서 생각한 두번째 풀이

n: 주어진 수(합한 값), a: 첫째항, k: 연속된 자연수의 개수

마지막항을 빼고 개수 k로 등차수열 식 세우고 두번째 항처럼 정리해준다.

그럼 이렇게 첫째항 공식을 세울 수 있는데, 이 때 첫째항이 k로 나눠져야지 무조건 자연수가 되기 때문에 이 공식을 활용해서 풀었다.

1. 위의 첫째항 공식에서 n-(k(k-1)) > 0 이여야 하기 때문에, for문의 조건을 k(k-1)/2 <n 으로 설정해줌.

2. 그리고 첫째항이 자연수가 되는 if문을 통해 조건에 맞다면 합공식이 성립하는 것이기 때문에 count를 증가시켜줌

  == (n-(k(k-1)/2) 이게 k로 나눴을 때 나머지가 0인 경우 count++ 

3. for문 다 돌면 count 반환해주기

// 등차수열 이용
// k : 연속된 자연수의 개수, n : 주어진 수
// 첫째항 = (n-(k(k-1))/2)/k
class Solution {
    public int solution(int n) {
        int count = 0;
        for(int k=1; k*(k-1)/2 < n; k++){
            if ((n-(k*(k-1)/2)) % k == 0){ // n - (k*(k-1))/2가 k로 나누어 떨어지면 합공식 성립
                count++;
            }
        }
        return count;
    }
}

 

 

간신히 효율성도 통과했다.....

힘들었다... 1씩 증가해서 더하는 for문으로 쉽게 풀 수 있었는데 괜히 등차수열 쓰고싶어서 복잡하고 어렵게 푼 듯. 다음에 다른 방식으로 풀어봐야겠다.