[Baekjoon/백준] 16139번: 인간-컴퓨터 상호작용(C/C++)

단계별로 풀어보기 17단계(누적 합) 3번 문제

https://www.acmicpc.net/step/48

누적 합 단계

---

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

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

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

---

문제 설명

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l, r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.

---

입력과 출력

입력: 첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1≤q≤200,000을 만족한다. 세 번째 줄부터 (q+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 αi와 0≤li≤ri<|S|를 만족하는 정수 li,ri가 공백으로 구분되어 주어진다.

출력: 각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 li번째 문자부터 ri번째 문자 사이에 αi가 나타나는 횟수를 출력한다.

서브태스크: 

• 문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.
• 추가 제한 조건이 없다.

---

접근 방법

이번 문제는 문자열 S와 질문의 수 q를 입력받고 q개의 질문(찾을 알파벳 소문자, 찾을 범위 시작 인덱스 번호, 찾을 범위의  마지막 인덱스 번호)을 입력받아서 그 결괏값을 출력하는 문제다. 쉽게 말하면 문자열에서 알파벳 소문자가 범위 내에 몇개 있는지 출력하는 것이다.

문자열을 입력받은 뒤, 문자열의 인덱스 번호와 저장된 알파벳 숫자를 저장한 이중 배열을 사용해서 누적합을 구하면 된다. 

예를 들어 예제처럼 seungjaehwang을 입력받았다면, 이중 배열 sum[0(인덱스)][0(알파벳 a~z)] = 1, sum[1][4] = 1, sum[2][15] = 1...과 같이 저장하면 된다. 저장할 때는 겹치는 글자가 나올 수 있으므로 이전 인덱스의 값들을 모두 불러와 누적한다.

이렇게 되면 문자열의 처음부터 각 인덱스까지 나온 문자의 개수들을 각각 저장할 수 있고, 이를 이용해서 r(마지막 인덱스 번호)에 l(찾을 범위의 시작 인덱스 번호) 이전의 인덱스(즉, l - 1)를 빼주기만 하면 문제 없이 해당 범위의 문자 개수들을 알 수 있다.

---

코드

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

int sum[200001][27];

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string S;
	int q;

	cin >> S;
	sum[0][S[0] - 'a']++;
	for (int i = 1; i < S.length(); i++) {
		for (int j = 0; j < 26; j++)
			sum[i][j] = sum[i - 1][j];
		
		sum[i][S[i] - 'a']++;
	}

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

		int count1 = l > 0 ? sum[l - 1][alphabet - 'a'] : 0;
		int count2 = sum[r][alphabet - 'a'];

		cout << count2 - count1 << "\n";
	}

	return 0;
}

---

결과

백준 제출 결과

이번 문제는 많이 틀렸다. 실수로 찾을 문자인 alphabet을 int로 하는 바람에... 덕분에 계속 쓸데없는 부분들만 정리하고 바꾸느라 여러번 더 틀렸다.

변수들을 무조건 계속 main 앞에다가 미리 선언해두는 것 때문에 발생했던지라, 이번부터는 코딩 스타일을 조금 바꿔서 위 코드처럼 반복문 같은 곳에서 쓰는 변수는 따로 사용할 때만 선언하기로 했다.