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

문제

https://programmers.co.kr/learn/courses/30/lessons/12924

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

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할

programmers.co.kr

풀이

0. 문제 해석

2022.02.09 - [알고리즘, 자료구조/기본] - [알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)

[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)

투 포인터 알고리즘이란? ▶ 1차원 배열에 존재하는 순차적 부분 배열에 접근해야 할 때 두개의 점을 활용하여 중복 연산을 줄이는 알고리즘 예시 문제를 활용하여 알아보자. 문제 : https://www.acmi

hanyeop.tistory.com

슬라이딩 윈도우를 활용하여 풀 수 있는 문제이다.

정답은 전부 연속된 자연수이므로 right 포인터는 항상 반복문의 i (맨 끝) 위치이다.

1부터 n까지 하나씩 더하면서 합을 구하고, 그 합이 n과 같다면 result 값을 늘려주고,

그 합이 n보다 커지면 left 포인터를 한 칸씩 앞으로 당겨오면서 그 값을 빼준다.

1. 전체 코드

// [프로그래머스] 숫자의 표현 (Java)
class Solution {
    
    public int solution(int n) {
        int answer = 0;
        int left = 0;
        int sum = 0;
        
        for(int i = 1; i <= n; i++){
            sum += i;
            
            // 범위에서 벗어나면 앞에서부터 줄여나가면서 범위에 맞춤
            while(sum > n){
                sum -= left;
                left++;
            }
            
            // 정답 찾을때 마다 ++
            if(sum == n){
                answer++;
            }
        }   
        return answer;
    }
}