[백준] 누적합 (16139 : 인간-컴퓨터 상호작용)

문제

---

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

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

---

해설

---

해당 문제는 문자열을 입력받고, 특정 문자와 구간을 다시 입력받아
특정 문자가 해당 구간에 몇개가 존재하는지 확인하는 문제이다.

예시를 통해서 알아보자.

알파벳\문자열	a	b	c	a	a	b
a	1	1	1	2	3	3
b	0	1	1	1	1	2
c	0	0	1	1	1	1
d	0	0	0	0	0	0
e	0	0	0	0	0	0
생략
y	0	0	0	0	0	0
z	0	0	0	0	0	0

위의 표를 보면 알 수 있듯, 문자열과 알파벳의 2차원 배열을 통해 누적합을 구하면

지금까지 풀었던 누적합 문제와 동일하게 접근하여 해결할 수 있다.

실제 코드에서는 행과 열이 표와 반대이지만, 아무튼 코트는 아래와 같다.

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static int cnt[][];
    public static void main(String[] args) throws IOException {
        String input = br.readLine();
        int N = Integer.parseInt(br.readLine());

        int sum[][] = new int[input.length()+1][26];
        for (int i = 0; i < input.length(); i++) {
            for (int j = 0; j < 26; j++) {
                int idx = input.charAt(i) - 'a';
                if (j == idx) {
                    sum[i+1][j] = sum[i][j] + 1;
                } else {
                    sum[i+1][j] = sum[i][j];
                }
            }
        }
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int idx = st.nextToken().charAt(0) - 'a';
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int res = sum[end+1][idx] - sum[start][idx];
            sb.append(res).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

1. 문자열의 누적합을 구하기 위해 chatAt() - 'a'를 통해 아스키코드를 이용하여 인덱스로 사용한다.
   idx가 현재 알파벳 순서와 같으면, 이전 문자열까지 나왔던 해당 알파벳의 개수에 1을 더해주고,
   다르다면, 그냥 이전 문자열까지 나왔던 해당 알파벳의 개수를 그대로 넘겨준다.
2. 이후, 알파벳과 구간을 입력받아, 빼주면 결과를 얻을 수 있다.

---

결론

---

문제는 메모리를 너무 많이 쓸까봐 걱정이 되는 문제여따.

---