[프로그래머스] 숫자의 표현 - Java

• 프로그래머스 등차수열의 개수 문제 링크

---

문제 요약

1부터 시작하는 연속된 자연수들의 합이 정확히 n이 되는 경우의 수를 구하는 문제다.

즉,
1 + 2 + ... + k = n 또는 3 + 4 + 5 + ... + m = n 같은 형태로
연속된 자연수들의 합이 n이 되는 모든 경우의 수를 세야 한다.

---

핵심 아이디어

이 문제는 1, 2, 3, ... 순서대로 연속된 자연수를 더해가는 가변 길이 슬라이딩 윈도우 접근이다.

핵심은 연속 합의 수학적 특성 활용:
연속된 k개 수의 합은 (첫항 + 끝항) * k / 2 형태로 표현된다.
하지만 투 포인터로는 자연수 배열을 가상으로 만들어 윈도우를 이동한다.

---

알고리즘 핵심 로직

start = 1, end = 1, sum = 1, answer = 0

while end <= n:
    if sum == n:
        answer++  // 이 길이의 연속합 발견
        sum -= start
        start++   // 다음 시작점으로 이동
    elif sum < n:
        end++
        sum += end
    else:  // sum > n
        sum -= start
        start++

특징: 배열 없이 인덱스를 값으로 직접 사용한다.

---

전체 코드 (제출용)

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

        int startIdx = 1;
        int endIdx = 1;
        int sum = 1;

        while (endIdx <= n) {
            if (sum == n) {
                answer++;
                sum -= startIdx;
                startIdx++;
            } else if (sum < n) {
                endIdx++;
                sum += endIdx;
            } else {
                sum -= startIdx;
                startIdx++;
            }
        }
        return answer;
    }
}

---

예제 시뮬레이션

입력: n = 15

탐색 과정:

• [15] → 합=15 ✓ (길이 1)
• [7, 8] → 7+8=15 ✓ (길이 2)
• [4, 5, 6] → 4+5+6=15 ✓ (길이 3)
• [1, 2, 3, 4, 5] → 1+2+3+4+5=15 ✓ (길이 5)

결과: 4

---

수학적 검증

연속합 공식: k개 연속수의 합 = k * (2a + (k-1)) / 2 = n
→ k * (2a + k - 1) = 2n (a: 시작값)

투 포인터가 이 식을 효율적으로 탐색하는 것이다.

---

핵심 포인트 정리

• 배열 없이 인덱스를 값으로 직접 사용하는 창의적 투 포인터
• 연속 자연수 합 패턴의 대표 예제
• 시간 복잡도: (O(\sqrt{n})) (end가 n까지만 이동)
• 수학적 통찰 + 구현 효율성의 완벽한 조합