[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java)

문제 링크

성능 요약

메모리: 106172 KB, 시간: 608 ms

분류

누적 합(prefix_sum)

문제 설명

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

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

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

입력

첫 줄에 문자열 $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$가 나타나는 횟수를 출력한다.

---

누적합을 활용하는 문제다.

처음에는 각 알파벳에 대응되는 배열을 map으로 선언하였는데, 그냥 2차원 배열로 풀어도 된다.

또, 시간 제한 때문에 BufferedReader를 써야 통과할 수 있었다.

누적합에서 그랬던 것처럼 모든 알파벳에 대해 그 알파벳이 몇번 나오는지 저장하면 된다.

0번 index에서 배열의 범위를 벗어나는 것을 방지하려고 문자열의 길이+1을 크기로 하는 배열을 선언하였다.

arr[i][j]는 i번째 문자열까지 알파벳 j(a가 0, b가 1)가 몇 번 나오는지를 기록한 것이다.

package Silver.s1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_16139_인간컴퓨터 {

    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        arr = new int[input.length() + 1][26];

        for (int i = 1; i <= input.length(); i++) {
            for (int j = 0; j < 26; j++) {
                arr[i][j] = arr[i - 1][j];
            }
            arr[i][input.charAt(i - 1) - 'a'] += 1;
        } // 알파벳 기준으로 누적합하기

        StringBuilder sb = new StringBuilder();

        int q = Integer.parseInt(br.readLine());
        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int key = st.nextToken().charAt(0) - 'a';
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            sb.append(arr[e + 1][key] - arr[s][key]).append("\n");
        }
        System.out.print(sb);

    }

}