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

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

 

문자열 S가 주어졌을 때, l 부터 r까지의 인덱스 중 알파벳 a의 개수를 출력하는 문제이다. a, l, r 이 q번 주어질 때마다 문자열을 일일이 탐색하여 해결할 수도 있겠지만 시간 초과가 발생할 것으로 예상된다. 

 

해당 문제는 구간합 개념으로 쉽게 해결할 수 있다.

 

0  1  2  3  4  5  6  7  8  9  10  11  12   //idx
s  e  u  n  g  j  a  e  h  w   a   n   g   //s[idx]
0  1  1  1  1  1  1  2  2  2   2   2   2   //idx까지 e개수의 누적합

 

구간합이란, 특정 구간의 값을 누적합을 통해 구하는 방법이다.

예를 들어, 위의 문자열에서 2번 부터 7번까지 알파벳 e의 개수는 1개이다. 

이는 7번까지의 알파벳 e 누적개수(2개) - 1번까지의 알파벳 e 누적개수(1개)로 구할 수 있다.

즉, l 부터 r 구간까지의 알파벳 등장 횟수는 r 까지의 알파벳 누적 횟수 - (l-1)까지의 알파벳 누적 횟수로 구한다.

 

문자열 s가 입력되었을 때 각 알파벳 'a' ~ 'z'에 대한 인덱스별 누적합을 구해놓는다면, 어떠한 알파벳이든 특정 구간에서의 등장 횟수를 쉽게 구할 수 있다.

 

psum[alpha][i] = (i == 0) ? 0 : psum[alpha][i-1];

 

psum[alpha][i]는 특정 소문자 alpha에 대한 인덱스 i까지의 누적 등장 횟수이다. 알파벳 소문자는 26개이므로, alpha의 값은 0~25가 된다. 기본적으로, 인덱스 i까지의 누적개수는 이전 누적 개수를 그대로 가져온다. 단, s[i]에 해당하는 문자열의 경우 인덱스 i까지의 누적 등장 횟수는 이전 누적개수에서 1을 더한 값이 된다.  

 

psum[s[i]-'a'][i]++;

 

(참고로, 알파벳들의 번호는 알파벳-'a'로 구한다. 알파벳 'a' 의 아스키코드는 97 이므로 'a'의 번호는 'a'-'a' = 0 이 된다. 알파벳 'z'의 아스키코드는 122 이므로 'z'의 번호는 'z'-'a' = 25가 된다.)

 

for (int i=0; i<s.size(); i++) {
	for (int alpha = 0; alpha < 26; alpha++)
	psum[alpha][i] = (i == 0) ? 0 : psum[alpha][i-1];
	psum[s[i]-'a'][i]++;
}

 

문자열이 입력된 직후 26개의 모든 알파벳 소문자에 대하여 특정 인덱스까지의 누적합을 구해놓는다.

문제에서 요구하는 값은 누적합이 아닌 l ~ r 까지의 개수이다. 

l = 0 이고, 0에서 r까지의 등장 횟수를 구해야 한다면, 인덱스 r까지의 누적합 psum[알파벳][r]을 출력한다.

나머지의 경우 인덱스 r까지의 누적합에서 (l-1)까지의 누적합을 뺀 psum[알파벳][r] - psum[알파벳][l-1]을 출력한다. 

 

printf("%d\n", (l == 0) ? psum[c-'a'][r] : psum[c-'a'][r]-psum[c-'a'][l-1]);

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

char c;
string s;
int q, l, r;
int psum[26][200000];

int main() {

    cin >> s;
    scanf("%d", &q);
    memset(psum, 0, sizeof(psum));

    for (int i=0; i<s.size(); i++) {
        for (int alpha = 0; alpha < 26; alpha++)
            psum[alpha][i] = (i == 0) ? 0 : psum[alpha][i-1];
        psum[s[i]-'a'][i]++;
    }

    while (q--) {
        scanf(" %c %d %d", &c, &l, &r);
        printf("%d\n", (l == 0) ? psum[c-'a'][r] : psum[c-'a'][r]-psum[c-'a'][l-1]);
    }
    return 0;
}