쌓고 쌓다

[프로그래머스] 연속 부분 수열 합의 개수 C++ 풀이 본문

알고리즘/프로그래머스

[프로그래머스] 연속 부분 수열 합의 개수 C++ 풀이

승민아 2023. 1. 23. 01:27

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이 방법

모든 인덱스에 대해 아래의 과정을 적용한다.

 

시작 인덱스(idx)에 시작하여 하나씩 인덱스를 증가하며 총합을 구한다.

하나씩 인덱스를 증가할때 배열의 끝에 도달하면 인덱스를 0으로 초기화하여 원형 수열 형태로 만든다.

하나씩 인덱스를 증가하며 해당 인덱스의 값을 더하여

총합을 구할때 map을 사용하여 총합이 처음 만들었다면 answer을 증가하고 map에 총합을 등록한다.

 

인덱스를 증가하며 원형 형태로 탐색할때, 시작 인덱스의 위치에 도달했다면

원형 끝까지 탐색한것이므로 탐색을 그만한다.

 

전체 코드

#include <string>
#include <vector>
#include <map>
using namespace std;
map<int, bool> m;

void sol(vector<int> v, int idx, int& answer) {
    
    // 시작 인덱스(idx)의 위치 값을 총합으로 초기화.
    int sum = v[idx];
    
    // 총합이 map에 존재하지 않으면 추가
    if (m.find(sum) == m.end()) {
        m.insert({ sum,true });
        answer++;
    }
    
    // 시작 인덱스는 검사했으니 다음 인덱스로 현재 인덱스(i)로 초기화.
    int i = idx+1;
    if (i >= v.size()) // 마지막 인덱스(총 크기)를 넘어선다면
        i = 0; // 0으로 초기화 (원형을 위해서)


    // 현재 인덱스 i가 시작 인덱스(idx)와 동일해지면 연속하는 모든 부분을 탐색한것임.
    // 그래서 i가 시작 인덱스가 될때까지 반복문을 돌릴것임.
    while (i!=idx) {
        sum += v[i]; // 현재 인덱스를 총합에 더함.
        if (m.find(sum) == m.end()) { // 총합이 존재하지않으면 map에 추가.
            m.insert({ sum,true });
            answer++;
        }
        
        i++; // 다음인덱스로 이동
        if (i >= v.size()) // 마지막인덱스를 넘어간다면 0으로 초기화.
            i = 0;
    }
}

int solution(vector<int> elements) {
    int answer = 0;
    
    // 모든 인덱스에 대해 연속 부분 탐색
    for (int i = 0; i <elements.size(); i++) {
        sol(elements, i, answer);
    }
    return answer;
}
Comments