[프로그래머스 - 자바(JAVA)] 35 : 숫자의 표현

목차

▸ 숫자의 표현

---

✅ 숫자의 표현 : Lv.2

▼ 문제

출처 : 프로그래머스 코딩테스트 연습 > 연습문제 > 숫자의 표현

▼ 내 풀이

• 일단 주어진 숫자 안에서 반복하면서 목표 숫자 n에서 숫자를 빼서 0이 되면 count+1 한다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i = 1; i <= n; i++) {
            int result = n-i;
            if(result == 0) {
                    answer++;
                    break;
                }
            for(int j = i+1; j <= n; j++) {
                result -= j;
                if(result == 0) {
                    answer++;
                    break;
                }
            }
        }
        return answer;
    }
}

• 결과
  
  • 정확성 테스트에서는 다 통과했지만 효율성 테스트에서는 통과하지 못했다.
  • 아무래도 중첩된 루프를 사용하여 모든 가능한 경우의 수를 탐색하기 때문에 시간 복잡도가 매우 높다고 생각한다.
  • 따라서, 등차수열의 합 공식을 사용해보았지만, 결과는 똑같았다. 코드가 조금 줄었다고 해도 중첩루프를 사용하기 때문에 그런 것 같다.

    class Solution {
        public int solution(int n) {
            int answer = 0;


            for(int i = 1; i <= n; i++) {
                for(int j = i+1; j <= n; j++) {
                    int result = (i+j)*(j-i+1)/2;
                    if(result == n) {
                        answer++;
                        break;
                    }
                }
            }
            return answer+1;
        }
    }

• 중첩 루프를 사용하지 않고 구하는 방법에 생각하다가 while문이 떠올랐다.
• 예제를 보면, 1-5까지 더한게 15인데 여기서 두번째 경우인 4-6을 얻기위해서는 15에서 1-3을 빼고 6을 더하면 된다.

  1 + 2 + 3 + 4 + 5 = 15
  4 + 5 + 6 = 15
  7 + 8 = 15
  15 = 15

• 즉, 더하고 빼는 것을 반복해야 하는데 현재 더해진 수가 15 보다 크면 더해져 있는 숫자를 빼고 15보다 작으면 새로운 숫자를 더한다.
• 시작점 start 와 끝점 end를 선언하고 while문을 end <= n일 경우에만 돌아가게 했다.
• 이 때, while문을 돌면서 start 와 end로 변해야하는데 현재 sum 값이 n 보다 크면 이전 수, 즉 start를 빼고 start++ 한다.
• end는 반대의 경우로 적용한다.
• 현재 sum 값이 n가 같을 경우 answer++ 하고 이전 숫자, start를 빼고 start++ 한다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int start = 1;
        int end = 1;
        int sum = 0;
        
        while (end <= n) {
            if (sum < n) {
                sum += end;
                end++;
            } else if (sum > n) {
                sum -= start;
                start++;
            } else {
                answer++;
                sum -= start;
                start++;
            }
        }
        
        return answer+1;
    }
}