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

문제, 입출력, 테스트케이스

해당 문제는 누적합을 이용해 푼 문제이다. 0번째 인덱스부터 시작한다는 것 때문에 1트에 틀렸지만 바로 고쳐서 패스하였다.

 

<문제 풀이/접근과정>
1. 문자열 길이 200,000이하, 문제 수 200,000이하, 인덱스는 0부터 시작
2. 알파벳 갯수는 26개이므로 문자열을 한 인덱스씩 읽어내려가며 누적합을 만들면 최대 26 * 200,000 = 5,200,000회 순회,  문제 200,000개 읽는데 200,000번 순회  = 5,400,000번 for문 순회하면 답이 나온다.
3. 알파벳 갯수가 26개인지 알 필요도 없이 char형 z - char형 'a' +1 하면 알파벳 갯수만큼 배열 선언 가능
4. 그냥 문자열에서 인덱스마다 문자 읽을 때 누적합 배열 채워준 뒤 문제 읽고 누적합 차를 통해 특정 구간의 합을 구하면 되는 문제

package boj;

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

public class Boj_16139 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int q = Integer.parseInt(br.readLine());
		int[][] sumAlphabet = new int[str.length() + 1]['z' - 'a' + 1]; // 알파벳 갯수만큼 존재해야함
		for (int i = 0; i < str.length(); i++) {
			for (int j = 0; j < sumAlphabet[i].length; j++) {
				if (str.charAt(i) - 'a' == j) {
					sumAlphabet[i+1][j] = sumAlphabet[i][j] + 1;
				} else {
					sumAlphabet[i+1][j] = sumAlphabet[i][j];
				}
			}
		}
		
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
			stz = new StringTokenizer(br.readLine());
			int key = stz.nextToken().charAt(0) - 'a';
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			sb.append(sumAlphabet[to+1][key] - sumAlphabet[from][key]).append("\n");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
	}
}

점심시간 30~40분에 알고리즘 풀기가 제일 효율적인 것 같다.