143. 16139(인간-컴퓨터 상호작용) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String S = br.readLine();
		int q = Integer.parseInt(br.readLine());
		int[] alphabetTmp = new int[26];
		int[][] alphabet = new int[S.length()][26];
		
		for (int i = 0; i < S.length(); i++) {
			alphabetTmp[S.charAt(i) - 'a']++;
			for (int j = 0 ; j < 26; j++) {
				alphabet[i][j] = alphabetTmp[j];
			}
		}

		for (int i = 0; i < q; i++) {
			String[] sBits = br.readLine().split(" ");
			char a = sBits[0].charAt(0);
			int l = Integer.parseInt(sBits[1]);
			int r = Integer.parseInt(sBits[2]);

			int tmp = 0;

			tmp = alphabet[r][a - 'a'];

			if (l != 0) {
				tmp -= alphabet[l - 1][a - 'a'];
			}

			sb.append(tmp).append("\n");
		}
		

		System.out.print(sb);
		
	}
}

문제요약

문자열에서 정해진 구간에 특정 문자가 몇개 있느냐?

설명

단순히 들어온 케이스마다 반복문으로 문제를 푼다면 100점을 맞을 수 없다.

 

카운팅정렬과 비슷하게 알파벳 26개를 지니는 배열을 정의하고 문자열의 각 문자에 대해 인덱스 값을 증가시켜 주어 처리한다.

 

글 만으로는 이해가 어려우니 표를 보자.

다음과 같이 seungjaehwang이 들어왔을 때, 각 문자에 해당되는 index는 위와같은 배열을 갖고 있다.

 

		for (int i = 0; i < S.length(); i++) {
			alphabetTmp[S.charAt(i) - 'a']++;
			for (int j = 0 ; j < 26; j++) {
				alphabet[i][j] = alphabetTmp[j];
			}
		}

이 코드를 통해서 위와같은 표를 만들 수 있는 것이다.

(값을 하나하나 넣어줘야 한다. 배열을 바로 덮어 씌우는 방법도 있지만 그러면 주소를 참조하여 값이 바뀌면 전에 넣었던 값도 같이 바뀐다.)

 

		for (int i = 0; i < q; i++) {
			String[] sBits = br.readLine().split(" ");
			char a = sBits[0].charAt(0);
			int l = Integer.parseInt(sBits[1]);
			int r = Integer.parseInt(sBits[2]);

			int tmp = 0;

			tmp = alphabet[r][a - 'a'];

			if (l != 0) {
				tmp -= alphabet[l - 1][a - 'a'];
                //누적합 이기때문에 -1을 해준다.
			}

			sb.append(tmp).append("\n");
		}

본격적으로 입력값에 대한 처리를 한다.

a는 문자 , l은 시작 구간, r은 끝 구간이다.

끝구간(r)에 입력 받은 문자(a) 의 인덱스에 해당되는 값을 가져온다.

 

주의) 0부터 처리한것이다. 만약 시작구간이 0번째가 아니라면 시작위치를 -1로 해준다.(누적합)