[백준][C++]16139번. 인간-컴퓨터 상호작용

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

 

소문자 문자열에 대한 누적합 배열을 만들어주고 이를 통해 문자열에 해당하는 구간에 얼마나 나오는지 구해주면 된다.

처음에 map을 사용하여 풀어보았는데 50점이 나왔다.

이유를 찾아보니 map에서 키를 관리할 때 이진 탐색트리를 사용하기 때문에 매 쿼리마다 이진 탐색 트리 과정이 추가로 들어가기 때문에 vector를 통해 알파벳에 접근하는 것이 더 효율적이다.

 

정답코드(map사용 : 50점)

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main()
{
	string s;
	cin >> s;

	int n = s.size();
	map<char, vector<int>> sum;

	// 누적 합 배열 초기화
	for (char c = 'a'; c <= 'z'; c++) {
		sum[c].resize(n + 1, 0);
	}

	// 누적 합 계산
	for (int i = 1; i <= n; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			sum[c][i] = sum[c][i - 1]; // 이전 값 복사
		}
		sum[s[i - 1]][i]++; // 현재 문자에 대한 값 증가
	}

	int q;
	cin >> q;

	for (int i = 0; i < q; i++)
	{
		char c;
		int l, r;
		cin >> c >> l >> r;

		int cnt = sum[c][r + 1] - sum[c][l];
		cout << cnt << "\n";
	}

	return 0;

}

정답코드(vector사용 : 100점)

#include <iostream>
#include <vector>

using namespace std;

int main() {


    string s;
    cin >> s;

    int n = s.size();

    // 알파벳 별 누적합 배열
    vector<vector<int>> sum(n + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            sum[i][j] = sum[i - 1][j]; // 이전 값을 복사
        }
        sum[i][s[i - 1] - 'a']++; // 현재 문자의 개수를 증가
    }

    int q;
    cin >> q;

    for(int i=0;i<q;i++) 
    {
        char c;
        int l, r;
        cin >> ch >> l >> r;

        int cnt = sum[r + 1][c - 'a'] - sum[l][c - 'a']; // 구간 계산
        cout << cnt << "\n";
    }

    return 0;
}