[백준] 16139 : 인간컴퓨터상호작용 (JAVA)

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

 

[풀이과정]

처음엔 구간을 나눠서 탐색했는데 50점 받았다.

값이 엄청 커져도 제대로 수행되려면 탐색을 줄여야 했기 때문에 누적합 방식으로 풂. 이게 맞는 방식이었다.

알파벳이 26개이니까 한 번의 탐색으로 str.index까지 알파벳이 몇 개 있는지 저장했고

(l, r) -> l - (r-1) 으로 값을 구했음

 

[코드-100점]

import java.io.*;
import java.util.*;
/*
특정 문자열, 특정 알파벳과 문자열의 구간 [l,r]
특정 알파벳이 몇 번 나타나는지 구하기
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String str;
    static int q;
    static int[][] alphabetSum;

    public static void main(String[] args) throws IOException {
        init();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < q; i++){
            st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            if(start == 0){
                sb.append(alphabetSum[c - 'a'][end]).append("\n");
            }
            else {
                sb.append(
                        alphabetSum[c - 'a'][end] - alphabetSum[c - 'a'][start - 1]
                ).append("\n");
            }
        }
        System.out.println(sb);
    }

    static void init() throws IOException{
        str = br.readLine();
        q = Integer.parseInt(br.readLine());
        alphabetSum = new int[26][str.length()];

        alphabetSum[str.charAt(0) - 'a'][0] = 1;
        for(int i = 1; i < str.length(); i++){
            char now = str.charAt(i);
            for(int j = 0; j < 26; j++) {
               alphabetSum[j][i] = alphabetSum[j][i-1];
            }
            alphabetSum[now - 'a'][i]++;
        }
    }
}

[코드-50점]

import java.io.*;
import java.util.*;
/*
특정 문자열, 특정 알파벳과 문자열의 구간 [l,r]
특정 알파벳이 몇 번 나타나는지 구하기
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String str;
    static int q;
    static int[][] info;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        init();
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < q; i++){
            st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            sb.append(method(l, r, c)).append("\n");
        }
        System.out.println(sb);
    }

    static void init() throws IOException{
        str = br.readLine();
        q = Integer.parseInt(br.readLine());
        info = new int[str.length()][2];//[][0]은 어디까지, [][1]은 개수
        visited = new boolean[str.length()];
    }

    static int method(int l, int r, char c){
        int cnt = 0;

        for(int i = l; i < r+1; i++){
            if(visited[i]){
                if(info[i][0] < r){
                    cnt += info[i][1];
                    i = info[i][0] + 1;
                    continue;
                }
            }
            if(str.charAt(i) == c){
                cnt++;
            }
        }

        info[l][0] = r;
        info[l][1] = cnt;

        return cnt;
    }
}