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

문제

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

알고리즘

투포인터 알고리즘

풀이

투포인터 알고리즘을 다시 기억하기 위해 풀어봤다.
두개의 포인터를 가지고 원하는 값보다 크면 start 포인터를 올리면서 sum을 감소시켜주고, 값이 작으면 end 포인터를 올리면서 sum에 더해준다.

코드

class Solution {
    public int solution(int n) {
        int answer = 1;
        int sum = 0;
        int start = 0;
        int limit = n / 2 + 1;
        int[] arr = new int[limit];

		// 2까지는 모두 1개의 방법밖에 없다.
		if (n < 3)
            return 1;
            
        // 자연수를 n까지 담아준다.
        for (int i = 0; i < limit; i++) {
            arr[i] = i + 1;
        }

		//end 포인터를 올려주면서 연속된 자연수가 n과 같은지 확인한다.
        for (int end = 0; end < limit; end++) {
        
        	// 일단 sum에 현재 인덱스의 값을 넣어준다.
            sum += arr[end];

			// 자기 자신도 방법에 포함되므로 넣어준다.
            if (sum == n) {
                answer++;
            }

			// 만약 sum이 n보다 크면 start 포인터를 올려주면서 start 인덱스의 값만큼 sum에서 빼준다.
            while (sum >= n) {
                sum -= arr[start++];

				// start 포인터를 올려서 sum에서 값을 빼주고 n이랑 같은지도 확인한다.
                if (sum == n) {
                    answer++;
                }
            }
        }

        return answer;
    }
}