[백준 16139] 인간-컴퓨터 상호작용

 

문제 : https://www.acmicpc.net/problem/16139

16139번: 인간-컴퓨터 상호작용

 

부분 합을 이용하는 문제.

일단 문자열의 각 알파벳이 어느 위치에서 나오는지를 입력받으면서 처리를 해줬다.

그다음 다시 각 알파벳별로 부분합을 구해준 뒤 문제를 풀면 된다~

 

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

vector<int> psum[26];
string str;

int range(int letter, int s, int e){
    if(s == 0) return psum[letter][e];
    return psum[letter][e] - psum[letter][s-1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> str;
    
    for(int i = 0; i < 26; i++)
        psum[i].resize(str.size());
    
    for(int i = 0 ; i < str.size(); i++){
        int letter = str[i] - 'a';
        
        // 알파벳이 나타나는 인덱스에 1을 표시.
        psum[letter][i] = 1;
    }
    
    for(int i = 0; i < 26; i++){
        // 각 알파벳 별로 부분합을 구해준다.
        partial_sum(psum[i].begin(), psum[i].end(), psum[i].begin());
    }
    
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        char c;
        int s, e;
        cin >> c >> s >> e;
        cout << range(c - 'a', s, e) << '\n';
    }
    
    return 0;
}

 

결과는 1,2번 다맞아서 100점 :)