백준16139(인간-컴퓨터 상호작용)

jh Seo·2022년 12월 27일

구간합배열 백준 한번에 푼 문제

백준

목록 보기

111/194

개요

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

입력
첫 줄에 문자열 $S$ 가 주어진다. 문자열의 길이는 $200,000$ 자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$ 가 주어지며, 문제의 수는 $1\leq q\leq 200,000$ 을 만족한다. 세 번째 줄부터 $(q+2)$ 번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 $\alpha_i$ 와 $0\leq l_i\leq r_i<|S|$ 를 만족하는 정수 $l_i,r_i$ 가 공백으로 구분되어 주어진다.
출력
각 질문마다 줄을 구분해 순서대로 답변한다. $i$ 번째 줄에 $S$ 의 $l_i$ 번째 문자부터 $r_i$ 번째 문자 사이에 $\alpha_i$ 가 나타나는 횟수를 출력한다.

접근 방식

전체 문자열의 길이 최댓값이 20만자이고, 질문수도 20만이라서
각 질문마다 문자열의 각 char형 원소를 판별하기엔 너무 오래걸린다.
극단적으로 20만개의 질문마다 index 0~ 20만까지 a가 몇개있냐를 물어볼때
index 0부터 20만까지 다 훑어보려면
20만*20만 이라 400억개의 연산을 해야해서 시간이 초과난다.
따라서 2차원 배열 alphabetInEachQuery[200'001][26]를 선언하여 각 순서당
알파벳이 몇개씩 있는지 체크를 하였다.
각 원소에서 알파벳의 첫번째 값인 'a'를 빼면 해당 알파벳의 index가 나오는점을 이용하였다.

	for (int i = 0; i < q; i++) {
		cin >> alphabet >> l >> r;
		//l을 포함해야하므로 l-1 번째부터 r번째 까지 
		cout << alphabetsInEachQuery[r + 1][alphabet - 'a'] - alphabetsInEachQuery[l][alphabet - 'a'] << '\n';
	}

코드

#include<iostream>

using namespace std;
string inputStr="";
//각 순서당 알파벳이 몇개씩 들어있는지 체크 
//510만*4 바이트정도-> 2백만 바이트 정도라 ㄱㄴ
int	alphabetsInEachQuery[200'001][27];

void Input() {
	int q=0,l=0,r=0,inputStrLen=0;
	char alphabet = 'a';
	cin >> inputStr;
	//반복문마다 계속 length함수 호출하는거 싫어서 미리 할당해놓음
	inputStrLen = inputStr.length();
	
	for (int i = 0; i < inputStrLen; i++) {
		for (int j = 0; j < 26; j++) {
			//alphabetsineachquery[i+1]은 i번째까지의 알파벳 갯수 합 
			alphabetsInEachQuery[i + 1][j] = alphabetsInEachQuery[i][j] + (j == inputStr[i] - 'a');

		}
	}
	cin >> q ;
	for (int i = 0; i < q; i++) {
		cin >> alphabet >> l >> r;
		//l을 포함해야하므로 l-1 번째부터 r번째 까지 
		cout << alphabetsInEachQuery[r + 1][alphabet - 'a'] - alphabetsInEachQuery[l][alphabet - 'a'] << '\n';
	}

}

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