[Baekjoon] 16139 - 인간-컴퓨터 상호작용

📝 문제

 

 

🔑 풀이 과정

· 문자열 길이, 질문의 수가 전부 최대 2*(10^5)이므로 매 질문마다 문자열 길이만큼 탐색해서 구하는 것(O(N^2))은 시간초과가 날 것이다. 누적합을 사용하되, 합 배열을 2차원으로 사용한다.

 

· 그림으로 표현한 것

 

· 단지 문자열의 i번째 문자를 카운팅하는것 뿐만 아니라, 그 전 행의 정보를 가져오는 것이 중요하다.

0번행은 가져올 정보가 없으니까 0번째 인덱스 문자만 카운팅해준다.

 

· l번째 문자와 r번째 문자사이에 알파벳이 나타내는 횟수를 구하려면 arr[r][알파벳] - arr[l-1][알파벳] 계산을 하면 된다. 여기서 l이 0일때는 arr[r][알파벳] 을 출력하게 하면 된다. (l-1 접근시 인덱스 에러)

 

 

 

🔓 답안

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        String S = br.readLine();
        int q = Integer.parseInt(br.readLine());

        int[][] arr = new int[S.length()][26];

        arr[0][S.charAt(0) - 'a']++;

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

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

            char alpha = st.nextToken().charAt(0);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int ans;
            if(start == 0)
                ans = arr[end][alpha - 'a'];
            else
                ans = arr[end][alpha - 'a'] - arr[start -1][alpha -'a'];

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

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 누적 합