BOJ 16139 - 인간-컴퓨터 상호작용 링크
(2023.06.12 기준 S1)

문제

특정 문자열 S가 주어진다. 특정 알파벳 a와 문자열의 구간 [l, r]이 주어지면 구간 안 a가 몇 번 나타나는지 출력해야 하는 쿼리가 q개 주어진다. 쿼리를 알맞게 처리.

알고리즘

누적 합

풀이

구간 [l, r]의 구간 합은 (r까지의 누적 합 - l-1까지의 누적 합)과 같다.

코드

• C++

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string S; cin >> S;
    int N = S.size(); // 문자열 S의 길이

    int prefix_sum[26][N + 1]; memset(prefix_sum, 0, sizeof(prefix_sum)); // 1-based index
    for (int i = 0; i < N; i++) prefix_sum[S[i] - 'a'][i + 1]++; // 인덱스마다 문자 카운트
    for (int i = 0; i < 26; i++) // 누적 합 배열 구하기
        for (int j = 1; j <= N; j++)
            prefix_sum[i][j] += prefix_sum[i][j - 1];

    int q, l, r; char a;
    cin >> q;
    while (q--){
        cin >> a >> l >> r;

        // [l, r] 구간 합은 prefix_sum[r] - prefix_sum[l - 1]
        cout << prefix_sum[a - 'a'][r + 1] - prefix_sum[a - 'a'][l] << '\n';
    }
}

• Python (PyPy3)

import sys; input = sys.stdin.readline

S = input().strip()
N = len(S) # 문자열 S의 길이

prefix_sum = [[0] * (N + 1) for _ in range(26)] # 1-based index
for i in range(N): # 인덱스마다 문자 카운트
    prefix_sum[ord(S[i]) - 97][i + 1] += 1
for i in range(26): # 누적 합 배열 구하기
    for j in range(1, N + 1):
        prefix_sum[i][j] += prefix_sum[i][j - 1]

for _ in range(int(input())):
    a, l, r = input().split()

    # [l, r] 구간 합은 prefix_sum[r] - prefix_sum[l - 1]
    print(prefix_sum[ord(a) - 97][int(r) + 1] - prefix_sum[ord(a) - 97][int(l)])