프로그래머스 연속 부분 수열 합의 개수

머리로는 어떻게 해야되는지 알겠는데, 진짜 코드로 로직을 짜는게 안된다.

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> elements) {
    
    int len = elements.size();
    set<int> results;
    
    
    elements.insert(elements.end(), elements.begin(), elements.end());
    
    
    for(int windowSize = 1; windowSize <= len; windowSize++) {
        
        int index = 0;
        int result = 0;
        queue<int> que;

        
        while(que.size() < windowSize) {
            que.push(elements[index]);
            result += elements[index];
            index++;
        }
        
        results.insert(result);
        
        for(int i = 0; i < len; i++) {
            que.push(elements[index]);
            result += elements[index];
            index++;
            
            result -= que.front();
            que.pop();
            results.insert(result);
        }
    }
    
    

    
    // for(auto x : results) {
    //     cout << x << "\n";
    // }
    return results.size();
}

 

 

조금 더 리팩토링 해봤다

#include <string>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int solution(vector<int> elements) {
    
    int len = elements.size();
    set<int> results;
    
    
    elements.insert(elements.end(), elements.begin(), elements.end());
    
    
    for(int windowSize = 1; windowSize <= len; windowSize++) {
        
        int index = 0;
        int result = 0;
        queue<int> que;
        
        for(int i = 0; i < len; i++) {
            
            while(que.size() < windowSize) {
                que.push(elements[index]);
                result += elements[index];
                index++;
            }
            results.insert(result);
            
            result -= que.front();
            que.pop();
        }
    }
    
    return results.size();
}

 

하지만 역시나 다른 사람들이 푼 풀이에 비하면 별볼일 없다.

이걸 나는 슬라이딩 윈도우 관점에서 봤는데, 어떤분은 각 자리에서 elements 길이만큼 더해가며 경우를 구하는 분도 있었다.

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    
    int len = elements.size();
    set<int> results;
    
    
    elements.insert(elements.end(), elements.begin(), elements.end());
    
    
    for(int i = 0; i < len; i++) {
        
        int result = 0;
        
        for(int j = i; j < i + len; j++) {
            
            result += elements[j];
            
            results.insert(result);
            
            
        }
        
    }
    
    return results.size();
}

 

이렇게 푸신 것이다. 역시나 매몰되면 안된다. 사고력이 제한이 된다.

 

머리 쓰는 시간을 자주 가져야겠다. 사고력이 필요하다. 둔해졌다.