[백준] 16139_인간-컴퓨터 상호작용 / 누적합

 

 

Sliver

 

 

문제

 

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

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

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

 

 

입력

 

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

 

 

출력

 

각 질문마다 줄을 구분해 순서대로 답변한다. 𝑖번째 줄에 𝑆의 𝑙𝑖번째 문자부터 𝑟𝑖번째 문자 사이에 𝛼𝑖가 나타나는 횟수를 출력한다.

 

---

 

풀이

 

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[][] al = new int[str.length()][26];      
        
        // 누적합 배열 생성
        for(int i=0; i<str.length(); i++){
            for(int j=0; j<26; j++){
                al[i][j] = al[i-1][j];
            }
            al[i][str.charAt(i)-'a']+=1;
        }

        for (int i=0; i<N;i++ ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            if(s==0) sb.append(al[e][c-'a']).append("\n");
            else sb.append(al[e][c-'a']-al[s-1][c-'a']).append("\n");
        }
        
        System.out.println(sb);
    }
}

 

해결방법

 

1. 누적합 배열 생성 : 배열 al[i][j]를 만들어 알파벳이 등장한 횟수를 누적하여 저장한다. 

2. al[e][c-'a'] - al[s-1][c-'a']를 통해 구간 내의 알파벳 등장 횟수를 계산한다. 만약 s가 0이라면 al[e][c-'a'] 를 사용한다. 

 

 

 

 

---

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