프로그래머스 숫자의 표현 JAVA 풀이 (투 포인터, 슬라이딩 윈도우)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

자연수 n이 주어질 때, 연속된 자연수들의 합으로 n을 표현할 수 있는 경우의 수를 구하는 문제이다.

예를 들어 15는 다음과 같이 표현할 수 있다.

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

따라서 정답은 4이다.

---

📌 접근 방법

연속된 자연수의 구간을 표현하기 위해 투 포인터를 사용한다.

start와 end를 이용하여 현재 구간을 나타내고, 현재 구간의 합을 sum으로 관리한다.

• sum < n 이면 구간이 부족하므로 오른쪽을 확장한다.
• sum > n 이면 구간이 크므로 왼쪽을 줄인다.
• sum == n 이면 정답을 증가시키고 다음 경우를 탐색한다.

이 과정을 반복하면 모든 연속 구간을 효율적으로 확인할 수 있다.

---

📌 핵심 아이디어

1. 현재 구간의 합 관리

현재 구간의 합을 저장하여 매번 다시 계산하지 않는다.

int start = 1;
int end = 1;
int sum = 1;

---

2. 합이 부족하면 구간 확장

현재 합이 n보다 작다면 더 큰 수를 포함시켜 합을 증가시킨다.

end++;
sum += end;

예시

1 + 2 + 3 = 6
↓
1 + 2 + 3 + 4 = 10

---

3. 합이 크면 구간 축소

현재 합이 n보다 크다면 가장 왼쪽 숫자를 제거한다.

sum -= start;
start++;

 

예시

1 + 2 + 3 + 4 + 5 + 6 = 21
↓
2 + 3 + 4 + 5 + 6 = 20

---

4. 합이 같으면 정답 증가

현재 구간이 정답이므로 개수를 증가시키고 다음 경우를 탐색한다.

answer++;

sum -= start;
start++;

예시

1 + 2 + 3 + 4 + 5 = 15

정답 카운트 후 다음 구간 탐색 진행

---

📌 전체 코드

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

        int start = 1;
        int end = 1;
        int sum = 1;

        while (start <= n) {

            if (sum == n) {
                answer++;
                sum -= start;
                start++;
            } else if (sum < n) {
                end++;
                sum += end;
            } else {
                sum -= start;
                start++;
            }
        }

        return answer;
    }
}

 

---

📄 정리

• 연속된 자연수의 합 문제는 투 포인터로 해결할 수 있다.
• start, end를 이용하여 현재 구간을 관리한다.
• sum < n이면 확장, sum > n이면 축소한다.
• sum == n이면 정답을 증가시킨다.
• 누적 합을 활용하면 불필요한 합 계산을 줄일 수 있다.