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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

투 포인터(Two Pointers), 슬라이딩 윈도우(Sliding Window), 탐색(Search)

 

---

 

 

 

처음 시도한 코드  -  테스트 케이스O,  효율성 테스트 X

 

#include <vector>
using namespace std;

int solution(int n) {
    int answer = 0;
    
    vector<int> v(n + 1);
    for(int i=0; i<=n; i++)
        v[i] = i;
    
    for(int i=1; i<=n; i++)
    {
        int x=0;
	    for(int j=1; j<=n; j++)
	    {
            if(i<=j)
            {
                x += v[j];

                if (x == n)
                {
                    answer++;
                }
            }
	    }
    }
    
    return answer;
}

 

테스트 케이스는 모두 통과하지만 효율성 테스트를 통과하지 못했다. 

 

---

 

 

 

실패한 코드

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;

    vector<int> v(n + 1);
    for(int i=1; i<=n; i++)
        v[i] = i;
    
    int start = 0, end = 0;
    int sum = 0;

    while (start <=n && end <=n)
    {
	    if(sum < n)
	    {
            sum += v[end++];
	    }
        else
        {
            if (sum == n) answer++;

            sum -= v[start++];
        }
    }

    
    return answer;
}

 

 

---

 

 

 

성공 코드

 

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    int answer = 0;

    for (int i = 1; i <= n; ++i) 
    {
        int sum = 0;

        for (int j = i; j <= n; ++j) 
        {
            sum += j;

            if (sum == n) 
            {
                ++answer;
                break;
            }

            else if (sum > n) 
                break;            
        }
    }

    return answer;
}

 

첫 번째 시도한 코드에서 vector 배열을 사용을 없앴다. break을 잘 활용하여 n과 같거나 큰 값이 되면 연산을 끝내고 다음 연산으로 넘어간다. 

 

---