프로그래머스 : 숫자의 표현 (JAVA)

문제

내용

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 이하의 자연수입니다.

입출력 예

n : 15

result : 4

문제 링크

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

프로그래머스

접근

첫 번째 방법

1. 이중 for문을 이용하여 완전 탐색을 한다.
2. 완전 탐색을 하면서 그 범위의 합이 n일 때 answer에 1을 더해준다.

 

두 번째 방법

투 포인터를 이용하여 연속되는 구간의 합이 n인 구간을 센다.

 

전체 코드

완전 탐색을 이용한 코드

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

        // 범위의 시작지점 (1 ~ n)
        for (int start = 1; start <= n; start++) {
            int sum = 0;
            // 시작지점부터 n까지 탐색
            for (int i = start; i <= n; i++) {
                // 범위의 합
                sum += i;

                // 범위의 합이 n일 때
                if (sum == n) {
                    answer += 1;
                    break;
                }
                // 범위의 합이 n보다 클 때
                if (sum > n) {
                    break;
                }
            }
        }

        return answer;
    }
}

투 포인터를 이용한 코드

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

        // 투 포인터를 위한 left, right 포인터
        int l = 1, r = 1;
        // (left ~ right) 범위의 합
        int sum = 1;
        while (l <= r && r <= n) {
            // 범위의 합이 n일 경우
            if (sum == n) {
                sum -= l++;
                sum += ++r;
                answer += 1;
                continue;
            }

            // 범위의 합이 n보다 클 경우
            if (sum > n) {
                sum -= l++;
                continue;
            }

            // 범위의 합이 n보다 작을 경우
            if (sum < n) {
                sum += ++r;
            }
        }

        return answer;
    }
}

코드 분석

투 포인터를 이용한 코드를 조금씩 나눠서 분석해 보도록 하자.

변수 선언 및 초기화

// 투 포인터를 위한 left, right 포인터
int l = 1, r = 1;
// (left ~ right) 범위의 합
int sum = 1;

• 투 포인터 를 이용하기 위해 left 포인터, right 포인터를 선언하고 둘 다 1로 초기화해 준다.
• left 포인터, right 포인터 사이에 있는 연속된 수들의 합을 저장할 sum을 선언하고, 현재 포인터가 둘 다 1을 가리키므로 1로 초기화해 준다.

투 포인터 시작

while (l <= r && r <= n) {
	// 범위의 합이 n일 경우
	// 생략..

	// 범위의 합이 n보다 클 경우
	// 생략..

	// 범위의 합이 n보다 작을 경우
	// 생략..
}

투 포인터 연산을 할 while문의 조건을 지정해 준다.

while) 범위의 합이 n일 경우

while (l <= r && r <= n) {
	// 범위의 합이 n일 경우
	if (sum == n) {
		sum -= l++;
		sum += ++r;
		answer += 1;
		continue;
	}

	// 범위의 합이 n보다 클 경우
	// 생략..

	// 범위의 합이 n보다 작을 경우
	// 생략..
}

범위의 합이 n일 경우 answer에 1을 더해주고, left, right 포인터 둘 다 1씩 늘려준다.

둘 다 늘리는 이유는 어차피 둘 중에 하나만 늘렸을 때 그 범위의 합이 다시 n이 되는 경우는 없기 때문이다.

• left만 늘렸을 때 다음 범위의 합: n - L (L = 원래 left가 가리키고 있던 값 > 0)
• right만 늘렸을 때 다음 범위의 합: n + R (R = 늘린 후 right가 가리키고 있는 값 > 0)

즉, 무조건 n보다 작거나 클 수밖에 없으므로 left와 right를 둘 다 1씩 늘려줘도 상관이 없다.

while) 범위의 합이 n보다 클 경우

while (l <= r && r <= n) {
	// 범위의 합이 n일 경우
	// 생략..

	// 범위의 합이 n보다 클 경우
	if (sum > n) {
		sum -= l++;
		continue;
	}

	// 범위의 합이 n보다 작을 경우
	// 생략..
}

범위의 합이 n보다 클 때는 현재 범위의 합을 줄여줘야 하므로 left를 1 늘려준다.

while) 범위의 합이 n보다 작을 경우

while (l <= r && r <= n) {
	// 범위의 합이 n일 경우
	// 생략..

	// 범위의 합이 n보다 클 경우
	// 생략..

	// 범위의 합이 n보다 작을 경우
	if (sum < n) {
		sum += ++r;
	}
}

반대로 범위의 합이 n보다 작을 때는 현재 범위의 합을 늘려줘야 하므로 right를 1 늘려준다.

 

입출력 예에서 포인터 변화 과정

n이 15일 때 left, right 포인터의 변화 과정을 전부 나타내보았다.

left, right 포인터가 각각 (1, 5), (4, 6), (7, 8), (15, 15) 일 때 answer가 하나씩 늘어나서 정답인 4가 return 되는 것을 알 수 있다.

 

 

후기

완전 탐색을 이용해도 통과가 되는 문제지만, 투 포인터를 연습하기 좋은 문제였던 것 같다. 개인적으로 투 포인터 문제에 취약하다고 느껴서 관련 문제를 더 풀면서 공부해 봐야겠다.