[알고리즘] 프로그래머스 : 숫자의 표현

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12924

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

 

내가 작성한 코드

i부터 j까지의 합을 1부터 j까지의 합에서 1부터 i-1까지의 합을 빼는 것으로 구할 수 있는 것을 활용해서 코드를 짰다. 예시로 나온 7+8=15라는 점에서 생각해서 j의 최댓값은 n의 절반보다 1이 더 크게, i의 최댓값은 n의 절반만큼으로 정하고 반복문을 돌렸는데 정확도는 곧바로 통과했으나 시간 복잡도에서 통과하지 못했다. 

class Solution {
    public int solution(int n) {
        int answer = 1;
        for(int i=1; i<=n/2; i++){
            for(int j=n/2+1; j>i; j--){
                if((j*(j+1)-i*(i-1))/2 == n){
                    answer += 1;
                }
            }
        }
        return answer;
    }
}

 

그래서 코드를 다시 작성했다. n*(n+1)/2를 쓰지 않고 1부터 차곡차곡 누적해서 더해가되 합이 n보다 커지면 n보다 작거나 같을 때까지 index 값을 빼준다. index는 1부터 시작해서 증가하며 결과적으로 1부터 i까지의 합에서 -1, -2, -3, ...을 순차적으로 해준 셈이 된다. 또 모든 수는 자기 자신을 포함하므로 애초에 answer는 시작할 때부터 1을 할당하고 들어갔고 이렇게 되면 반복문을 n/2+1번만 돌려주면 된다.

class Solution {
    public int solution(int n) {
        int answer = 1;
        int total = 0;
        int index = 1;
        for(int i=1; i<=n/2+1; i++){
            total += i;
            if(total > n) {
                while(total > n) {
                    total -= index;
                    index++;
                }
            }
            if(total == n) {
                answer += 1;
            }
        }
        return answer;
    }
}