백준 16139 인간-컴퓨터 상호작용

 

간단한 dp 문제로 접근해서 풀었다.

흐름은 다음과 같다.

 

1. 2차원 배열 int[][] dp = new int[알파벳의 개수][글자의 자리수] 로 설정한다.

     (3번째 자리까지의 c의 dp값은 dp['c' - 'a'][3])이다.

2. dp를 돌려주는데  해당 알파벳인 경우 dp[][i] = dp[][i-1] + 1;을 해주고 이외의 경우에는 dp[][i] = dp[][i-1]을 해준다

3. a ~ b번째 자리수의 경우 dp[][b]  - dp[][a-1] 로 접근하면 되므로 이렇게 return하는 함수를 만든다. 

 

subtask가 있으므로 scanner대신 BufferReader와 StringBuilder 이용했다.

package programers;

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

public class BOJ_16139 {
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        dp = new int[26][str.length];
        dp[str[0] - 'a'][0] =1;
        int length = str.length;
        for(int i = 1; i < length; i++) {
            for(int j = 0; j < 26; j++) {
                dp[j][i] = dp[j][i-1];
            }
            dp[str[i]-'a'][i]++;
        }
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            sb.append(find(s)+"\n");
        }
        System.out.println(sb);
    }
    private static int find(String[] s) {
        char c = s[0].charAt(0);
        int start = Integer.parseInt(s[1]);
        int end = Integer.parseInt(s[2]);
        if(start == 0) return dp[c-'a'][end];
        else return dp[c-'a'][end] - dp[c-'a'][start-1];
    }
}