split()

문자열을 split()하는 로직은 코딩테스트에 많이 등장하지만, C++의 STL에서는 split() 함수를 지원하지 않기 때문에 만들어야 한다.

시간복잡도 : O(n)

#include<bits/stdc++.h>
using namespace std;

vector<string> split(string input, string delimiter) {
    vector<string> ret;
    long long pos = 0;
    string token = "";
    while ((pos = input.find(delimiter)) != string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos + delimiter.length());
    }
    ret.push_back(input);
    return ret;
}

int main() {
    string s = "특정 문자열을 찾아 위치를 반환!", d = " ";
    vector<string> a = split(s, d);
    for(string b : a) cout << b << '\\n';
}

// delimiter : 구분자
// find(문자열)  : 특정 문자열을 찾아 위치를 반환. 만약 해당 문자열을 못 찾을 경우 string::npos를 반환, O(n)의 시간복잡도
//                string::npos는 size_t 타입의 최댓값을 의미한다. 
// substr(위치, 크기) : 특정 위치에서 크기만큼의 문자열을 추출. O(n)의 시간복잡도
// erase(위치, 크기) : 특정 위치에 크기만큼 문자열을 지움. O(n)의 시간복잡도

// 출력
특정
문자열을
찾아
위치를
반환!

누적합 (prefix sum)

#include<bits/stdc++.h>
using namespace std;

int a[100004], b, c, psum[100004], n, m;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        psum[i] = psum [i - 1] + a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b >> c;
        cout << psum[c] - psum[b - 1] << "\\n";
    }
    return 0;
}