[프로그래머스/자바] 숫자의 표현

class Solution {
    public int solution(int n) {
        int[] sum = new int[n + 1];
        
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + i;
        }
        
        int count = 0;
        int start = 0;
        
        for (int i = 1; i < sum.length; i++) {
            int tmp = sum[i] - sum[start];
            if (tmp == n) {
                count++;
                start++;
                i = start;
            } else if (tmp > n) {
                start++;
                i = start;
            }
        }
        
        return count;
    }
}

---

* 효율성 테스트 실패 코드

class Solution {
    public int solution(int n) {
        int[] arr = new int[n + 1];
        
        for (int i = 1; i < arr.length; i++) {
            arr[i] = i;
        }
        
        int[] sum = new int[arr.length];
        
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }
        
        int count = 0;
        
        for (int i = sum.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (sum[i] - sum[j] == n) count++;
            }
        }
        
        return count;
    }
}

arr 배열은 굳이 생성할 필요가 없고, if문 조건식에 맞는 경우 배열 순환의 단계를 뛰어넘어야 한다.