백준 16139 c++ "인간-컴퓨터 상호작용"

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

[필자 사고]

단순 브루트포스 알고리즘을 이용하면 N==200000 이기 때문에 시간초과가 발생한다.

그래서 사전에 누적합을 이용하여 미리 문자의 갯수를 갱신해 놓은 상태로 문제를 해결했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입출력 최적화

가장 먼저, 입출력 속도를 빠르게 하기 위해 표준 입출력 동기화를 끊고, 입출력 묶음을 분리해 속도를 높인다. 이는 대규모 데이터가 들어올 경우 성능에 큰 차이를 만든다.

---

2. 입력 처리

문자열 S와 쿼리의 개수 q를 입력받는다. 이후 문자 별 등장 횟수를 빠르게 계산할 수 있도록 전처리를 진행한다. 이를 위해 2차원 배열을 사용하여 알파벳마다 누적 등장 횟수를 저장할 수 있는 구조를 만든다.

---

3. 누적합 배열 구성

문자열을 처음부터 끝까지 순회하면서, 각 위치까지의 알파벳 등장 횟수를 누적해 저장한다. 이때 각 알파벳마다 26개의 행을 사용해 관리하며, i번째 열은 문자열의 0번째부터 i번째까지의 누적 정보를 의미한다. 특정 위치에서 특정 문자가 몇 번 나왔는지 빠르게 조회할 수 있도록 미리 계산해두는 것이다.

---

4. 쿼리 처리

각 쿼리는 문자 하나와 구간의 시작과 끝 인덱스를 입력받는다. 그 후, 누적합 배열을 활용하여 해당 문자에 대한 구간 내 등장 횟수를 상수 시간 안에 계산한다. 구간의 시작이 0일 경우에는 해당 인덱스까지의 누적값이 그대로 정답이 되며, 그렇지 않은 경우에는 누적값의 차이를 이용해 정답을 구한다.

[소스 코드]

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

// 50점 맞은 이유는 서브태스크 1의 문자열 길이 2000자를 보고 문제를 풀어서 그럼, 위에 문제에서는 q가 200,000까지 가능하다고 해서 혹시나 해서 범위를 2001에서 200001로 키웠더니 100점 맞음
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string S;
    int q, start, end;
    int counts[27][200001];
    char letter;

    cin >> S >> q;
    counts[S[0] - 'a'][0] = 1;
    for (int i = 1; i < S.size(); i++)
    {
        for (int j = 0; j < 27; j++)
        {
            counts[j][i] = counts[j][i - 1];
        }
        counts[S[i] - 'a'][i]++;
    }
    for (int i = 0; i < q; i++)
    {
        cin >> letter >> start >> end;
        int temp = letter - 'a';
        if (start == 0)
            cout << counts[letter - 'a'][end] << '\n';
        else
            cout << counts[letter - 'a'][end] - counts[letter - 'a'][start - 1] << '\n';
       
    }

    return 0;
}