[백준] 16139번(Java)

📖 인간-컴퓨터 상호작용

[ 문제 ]
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $q$번 할 것이다.

💡풀이

• 주어진 문자열 중 나타나는 알파벳들을 중복 없이 alp라는 String 변수에 담는다.
• 누적합 원리를 바탕으로 특정 위치까지 해당 알파벳이 몇 개 누적되었는지를 2차원 배열에 담는다.
• 위치 $l$, $r$의 값이 나오면 해당 알파벳 누적합의 $r$위치 값과 $l$위치 값의 차이를 바탕으로 해당 구간 내 알파벳의 개수를 구한다.
• 처음에 중복된 알파벳 그대로 계산을 했더니 50점만 줬다. (기분 나빠)
• 중복처리를 하지 않을 경우 문자열 길이가 200,000자 이하이기 때문에 $O(n^2)$의 시간 복잡도를 가지는 계산 때문에 서브태스크 2에서 점수를 받지 못했던 것 같다.

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

public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] S = br.readLine().split("");   // 문자열
        int n = S.length;
        String alp = "";

        for(int i = 0 ; i < S.length; i ++){
            if(!alp.contains(S[i])) alp += S[i];
        }
        int m = alp.length();

        int q = Integer.parseInt(br.readLine());   // 질문 수
        int[][] cadd = new int[m + 1][n + 1];

        for(int i = 0; i < m ; i ++){
            int tmp = 0;
            for(int j = 0; j < n; j ++){
                if(String.valueOf(alp.charAt(i)).equals(S[j])) tmp += 1;
                cadd[i + 1][j + 1] = tmp;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int k = 0; k < q ; k ++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int loc = alp.indexOf(a);

            sb.append(cadd[loc + 1][r + 1] - cadd[loc + 1][l]).append("\n");
        }
        System.out.println(sb);
    }
}

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