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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12924

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

 

n이 10000 이하의 자연수일 때,

연속된 자연수의 합으로 n을 표현할 수 있는 경우의 수를 구하는 문제입니다.

 

우선 이 문제를 푸는 가장 간단한 방법을 생각해 봅시다.

int count = 0;

for (int i = 1; i <= n; i++) {
	int sum = 0;
    for (int j = i; j <= n; j++) {
    	if (sum < n) {
        	sum += j;
    	}
        else if (sum == n) {
        	count++;
            break;
        }
        else {
        	break;
        }
    }
}

아래와 같은 코드를 작성하면, 1부터 n까지 모든 자연수로 시작하는 수열의 경우의 수를 탐색합니다.

[1 + 2 + ... ], [2 + 3 + 4 + ...], [3 + 4 + ...] ... [n] 처럼 모든 수열의 합을 구하고 n과 비교해 볼 것입니다.

 

위 코드로 해결되지 않는 점은, 이 문제는 효율성 테스트도 있다는 점입니다.

n  <= 10,000이고, 위 코드는 O(n^2)의 시간 복잡도를 가지게 됩니다.

즉 10,000 ^ 2 = 100,000,000의 연산 횟수를 가지게 되고, 아마 이 문제를 푸는 가장 효율적인 방법은 아닐 것입니다.

 

위 코드에서 찾은 문제점은, 같은 결과를 여러번 구한다는 점입니다.

간단한 예시를 들어 보겠습니다.

1부터 시작하는 수열에서도 1 + 2 + 3을 하고, 2부터 시작하는 수열에서도 2 + 3을 합니다.

이것이 반복되면 불필요한 합 연산이 반복되는 것입니다.

 

제가 생각한 방법은 아래와 같습니다.

먼저, 1과 n 사이에서, 수열의 시작과 끝을 나타내는 start, finish 변수를 둡니다. 둘 모두 시작 위치는 1입니다.

또, 현재 누적 합 값을 담는 sum 변수를 둡니다. 이 값 역시 시작 값은 1입니다.

 

이후, finish가 n 이하일 동안 아래 과정을 반복합니다.

• sum이 n보다 작다면, sum의 값을 키워야 합니다. finish의 값을 하나 증가시키고, finish의 값을 sum에 더합니다.
• sum이 n보다 크다면, sum의 값을 줄여야 합니다. sum에서 start의 값을 빼고, start의 값을 하나 증가시킵니다.
• sum이 n과 같다면, 문제에서 찾는 경우의 수를 하나 찾은 것입니다. answer의 값을 하나 증가시킵니다. 이어서, 다음 경우의 수를 찾기 위해 finish의 값을 하나 증가시키고, finish의 값을 sum에 더합니다.

일종의 투 포인터 알고리즘을 이용하여 반복 연산을 줄이는 접근법입니다.

 

코드 링크: GitHub

GitHub - kchung1995/code_test_personal: 혼자 코딩 테스트 공부를 하며 사용하는 저장소

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12924
#include <string>
#include <vector>

using namespace std;

int start = 1, finish = 1;
int sum = 1;

int solution(int n) {
    int answer = 0;
    
    if (n == 1) return 1;
    
    while (finish <= n) {
        if (sum < n) {
            finish++;
            sum += finish;
        }
        else if (sum > n) {
            sum -= start;
            start++;
        }
        else if (sum == n) {
            answer++;
            finish++;
            sum += finish;
        }
    }
    
    return answer;
}

 

이 방법으로 효율성 테스트까지 전부 통과하였습니다.

시간이 오래 걸리지 않는 것으로 보여 뿌듯하네요 ㅎㅎ