[백준] #16139. 인간-컴퓨터 상호작용 (실버 1)

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

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String S = br.readLine();  //문자열
		int q = Integer.parseInt(br.readLine());  //질문의 수

		int n = S.length();  // 문자열의 길이

		// 각 문자의 누적합을 저장할 2차원 배열
		int[][] prefixSum = new int[26][n + 1];

		// 누적합 계산
		for (int i = 0; i < n; i++) {
			int charIndex = S.charAt(i) - 'a';  // 문자를 인덱스로 변환
			for (int j = 0; j < 26; j++) {
				prefixSum[j][i + 1] = prefixSum[j][i] + (j == charIndex ? 1 : 0);
			}
		}


		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());

			char alpha = st.nextToken().charAt(0);
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());

			int charIndex = alpha - 'a';  // 문자를 인덱스로 변환
			// 해당 문자의 누적합 배열에서 범위 내 등장 횟수 계산
			int count = prefixSum[charIndex][r + 1] - prefixSum[charIndex][l];

			sb.append(count).append("\n");  // 결과 저장
		}

		System.out.print(sb);
	}
}

 

주의할 점

1. 전처리 단계
   - 각 문자에 대해 누적 등장 횟수를 저장하는 2차원 배열 `prefixSum`을 만듭니다. (알파벳 소문자 전체 26개)

		// 각 문자의 누적합을 저장할 2차원 배열
		int[][] prefixSum = new int[26][n + 1];

   - `prefixSum[j][i]`는 문자 `j`가 문자열의 0번째부터 i번째까지 등장한 횟수를 나타냅니다. (j에는 문자를 인덱스로 변환 시의 값)
   - 문자열 S를 순회하며 각 문자의 등장 횟수를 누적하여 `prefixSum` 배열에 저장합니다.
   - 시간 복잡도 : O(26×N)

		// 누적합 계산
		for (int i = 0; i < n; i++) {
			int charIndex = S.charAt(i) - 'a';  // 문자를 인덱스로 변환
			for (int j = 0; j < 26; j++) {
				prefixSum[j][i + 1] = prefixSum[j][i] + (j == charIndex ? 1 : 0);
			}
		}

 

2. 질의 처리 단계
   - 각 질의에 대해, `prefixSum` 배열을 사용해 범위[l,r] 내의 해당 문자의 등장 횟수를 계산합니다.
   - 시간 복잡도 : O(1)

			int charIndex = alpha - 'a';  // 문자를 인덱스로 변환
			// 해당 문자의 누적합 배열에서 범위 내 등장 횟수 계산
			int count = prefixSum[charIndex][r + 1] - prefixSum[charIndex][l];