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

 이 문제는 투 포인터를 이용해서 푸는 문제이다. 입력이 최대 10,000 인 자연수이기 때문에, 벡터에 숫자들을 넣어서 풀기에도 충분했다. 숫자 배열에는 1부터 n까지만을 넣으면 되는데, n보다 더 큰 숫자들이 들어가면 음수가 있지 않는 이상은 절대 n을 만들 수 없기 때문이다.

 

 투 포인터에서 왼쪽에서 둘 다 출발하는 방식으로 구현했다. 이 때 유의해야 할 점은 acc가 적용되는 범위를 [left, right]로 할 것이냐 [left, right) 로 할 것이냐였는데, 더 직관적인 전자를 선택해서 구현했다. 이 때 right을 먼저 더하고 해당 인덱스에 대한 숫자를 더하는데, right++을 한 상태에서 배열 범위를 벗어나면 오류가 발생하므로 매 분기마다 확인해줘야 한다.

 

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<int> numbers;
    
    for (int i = 1; i <= n; i++) {
        numbers.push_back(i);
    }
    
    int left = 0;
    int right = 0;
    int acc = numbers[left];
    
    while (left <= right && right < n) {
        if (left != right) {
            if (acc < n) {  // 작을 때
                right++;
                if (right < n) {
                    acc += numbers[right];
                }
            }
            else if (acc > n) { // 클 때
                acc -= numbers[left];
                left++;
            }
            else {
                answer++;
                right++;
                if (right < n) {
                    acc += numbers[right];
                }
            }
        }
        else {
            if (acc == n) {
                answer++;
            }
            right++;
            if (right < n) {
                acc += numbers[right];
            }
        }
    }
    
    return answer;
}