[BOJ-16139][C++] 인간-컴퓨터 상호작용

문제

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

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

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

 

입력

첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 q가 주어지며, 문제의 수는 1≤q≤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$가 나타나는 횟수를 출력한다.

 

서브태스크 1 (50점)

문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.

 

서브태스크 2 (50점)

추가 제한 조건이 없다.

 

예제 입력 1

seungjaehwang
4
a 0 5
a 0 6
a 6 10
a 7 10

 

예제 출력 1 

0
1
2
1

 

출처

University > 광주과학기술원 > 광주과학기술원 HOLICS 알고리즘 대회 2018 B번

 

알고리즘 분류

• 누적 합

 

채점 및 기타 정보

• 예제는 채점하지 않는다.

 

문제 출처

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

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

 

---

 

문제 해결 방법

• 누적 합 알고리즘을 이용하여 풀 수 있었던 문제였다.
• 우선 소문자 @a@의 아스키 코드는 @97@이라는 사실을 알고 있어야 한다.
• 입력 받은 문자열(@S@)의 첫번째 문자부터 마지막 문자까지 순환을 하며 @a@부터 @z@ 알파벳이 들어있는 위치의 누적 합을 2차원 배열(@pSums@)에 저장한다.
  • 순환을 하며 문자열 @S@의 특정 문자가 입력 받은 알파벳(@alpha@)과 비슷할 경우 그 값을 1 증가시켜준다.
    • @if (S[j] == (char)(i + 97)) { pSums[i][j]++; }@
  • 동시에 누적 합을 수행한다.
    • @pSums[i][j] += pSums[i][j - 1];@

cin >> S >> q;

for (int i = 0; i < 26; i++) {
    for (int j = 0; j < S.size(); j++) {
        if (S[j] == (char)(i + 97)) {
            pSums[i][j]++;
        }
        pSums[i][j] += pSums[i][j - 1];    // 누적 합 수행
    }
}

• 이 과정을 수행하면 문자열 @S@에 포함된 @a@부터 @z@까지의 각 문자들 위치의 누적 합을 구할 수 있다. 
• 이 과정을 @예제 입력 1@의 케이스에 적용하면, 2차원 배열은 다음과 같이 채워진다.

idx	0	1	2	3	4	5	6	7	8	9	10	11	12
S	s	e	u	n	g	j	a	e	h	w	a	n	g
a	0	0	0	0	0	0	1	1	1	1	2	2	2
b	0	0	0	0	0	0	0	0	0	0	0	0	0
c	0	0	0	0	0	0	0	0	0	0	0	0	0
d	0	0	0	0	0	0	0	0	0	0	0	0	0
e	0	1	1	1	1	1	1	2	2	2	2	2	2
f	0	0	0	0	0	0	0	0	0	0	0	0	0
g	0	0	0	0	1	1	1	1	1	1	1	1	2
h	0	0	0	0	0	0	0	0	1	1	1	1	1
i	0	0	0	0	0	0	0	0	0	0	0	0	0
j	0	0	0	0	0	1	1	1	1	1	1	1	1
k	0	0	0	0	0	0	0	0	0	0	0	0	0
l	0	0	0	0	0	0	0	0	0	0	0	0	0
m	0	0	0	0	0	0	0	0	0	0	0	0	0
n	0	0	0	1	1	1	1	1	1	1	1	2	2
o	0	0	0	0	0	0	0	0	0	0	0	0	0
p	0	0	0	0	0	0	0	0	0	0	0	0	0
q	0	0	0	0	0	0	0	0	0	0	0	0	0
r	0	0	0	0	0	0	0	0	0	0	0	0	0
s	1	1	1	1	1	1	1	1	1	1	1	1	1
t	0	0	0	0	0	0	0	0	0	0	0	0	0
u	0	0	1	1	1	1	1	1	1	1	1	1	1
v	0	0	0	0	0	0	0	0	0	0	0	0	0
w	0	0	0	0	0	0	0	0	0	1	1	1	1
x	0	0	0	0	0	0	0	0	0	0	0	0	0
y	0	0	0	0	0	0	0	0	0	0	0	0	0
z	0	0	0	0	0	0	0	0	0	0	0	0	0

• 이렇게 2차원 배열을 채워 넣었다면, @alpha@, @l@, @r@ 값을 입력 받아 누적 합 알고리즘을 적용하여 해당 위치에 있는 문자의 개수를 출력시킨다.
• 구간 @[l, r]@의 누적 합을 구하는 알고리즘은 @pSums[r] - pSums[l - 1]@이다. 하지만, @l@이 @0@일 경우 배열의 범위를 넘어가기 때문에 @pSum[r]@만 출력하도록 하여 예외 처리를 해주어야 한다.

int answer;
        
if (l == 0) {
    answer = pSums[alpha - 'a'][r];
}
else {
    answer = pSums[alpha - 'a'][r] - pSums[alpha - 'a'][l - 1];
}
cout << answer << '\n';

 

코드

#include <iostream>
using namespace std;

string S;
char alpha;
int q, l, r;
int pSums[27][200001];

void Solve() {
    cin >> S >> q;

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < S.size(); j++) {
            if (S[j] == (char)(i + 97)) {
                pSums[i][j]++;
            }
            pSums[i][j] += pSums[i][j - 1];    // 누적 합 수행
        }
    }
    
    for (int i = 0; i < q; i++) {
        cin >> alpha >> l >> r;
        
        int answer;
        
        if (l == 0) {
            answer = pSums[alpha - 'a'][r];
        }
        else {
            answer = pSums[alpha - 'a'][r] - pSums[alpha - 'a'][l - 1];
        }
        cout << answer << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [누적 합]
• 실버I

 

누적 합(Prefix Sum)

• https://dev-astra.tistory.com/205

[Algorithm] 부분합(Partial Sum) ; 누적합(Prefix Sum)