프로그래머스 레벨2 숫자의 표현

• 숫자의 표현

문제 설명

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

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

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

• n은 10,000 이하의 자연수 입니다.

---

입출력 예nresult

15

4

 

슬라이딩 윈도우 문제로 풀면 된다. 이전에 어려운 문제로 슬라이딩 윈도우를 마주쳤을때는 뭐 이런 문제가 다있나 싶었는데 간단한 문제로 보니 이해가 더 잘된다. 아니면 이미 경험했던 거라 그런가..?

left        right
  1 2 3 4 5 = 15   sum==n
여기서 맨 앞 숫자를 빼면  sum-=++left 
2+3+4+5 < 15 로 6을 더해준다 sum+=++right

2+3+4+5+6 = 15 가 된다. sum==n
다시 맨 앞 숫자를 빼면 sum-=++left 
3+4+5+6 < 15 로 7을 더해준다 sum+=++right

3+4+5+6+7 =25 15초과해 맨 앞숫자를 뺀다. sum+=++right
4+5+6+7 =22 15를 초과하므로 맨 앞숫자를  빼준다. sum-=++left 
5+6+7 =18 15를 초과하므로 맨 앞숫자를 빼준다. sum-=++left 
6+7+8 = 21 15를 초과하므로 맨 앞숫자를 빼준다. sum-=++left 
7+8=15 15를 만족한다.  sum==n

이후 15 = 15를 만족하므로 총 4가지가 답이 된다.  sum==n

 

아, 맨 마지막경우인 자기자신이 경우의 수 일때는 검사 안하는대신 answer=1로 설정해 둠, n=1, 2 일때는 그대로 1리턴됨.

 class Solution {

	    public int solution(int n) {//-슬라이딩 윈도우
	    	int answer=1;
	    	if(n<3) return answer;
	    	//3~
	    	int sum=1; 
	    	int left=1; int right=2; //더할때는 right를 증가시키며 더하고, 뺄때는 left를 증가시키며 빼기

	    	while(right<n) {
	    		if(sum>n) {//sum을 줄여야됨
	    			sum-=left;
	    			left++;
	    		}else if(sum<n) {//sum을 늘리자
	    			sum+=right;
	    			right++;
	    		}

	    		if(sum==n) {//같을때 answer증가, 미리 젤작은수 빼서 다시 돌게하기
	    			answer++;
	    			sum-=left;
	    			left++;
	    		}
	    	}

	        return answer;
	    }
	}