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

1. 문제

16139번: 인간-컴퓨터 상호작용

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

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

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

---

2. 풀이

1.  문자열 S를 char[]로 바꾼 후 하나씩 탐색하면서 count[26][S길이] 배열에 알파벳을 하나씩 카운팅한다.

2.  count배열을 누적합 배열로 만든다. 이전 요소를 현재 요소에 더하면 된다.

3.  N을 입력받고 그 수만큼 반복하며 질문을 수행한다. 알파벳 종류는 미리 'a'를 빼서 int로 바꿔놓는다.

4.  count배열을 1부터 쓰도록 만들었으므로 l은 그대로 두고 r에 +1한다. (l값을 포함하려면  l입력값 -1을 해야했는데, l+1-1=l이기 때문)

5.  sb에 count[알파벳][r]-count[알파벳][l]한 값을 더한다.

6.  출력한다.

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

public class BOJ_16139_인간컴퓨터상호작용 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      char[] S = in.readLine().toCharArray();

      //저장
      int[][] count = new int[26][S.length+1];
      for(int i=1;i<=S.length;i++){
         count[S[i-1]-'a'][i]++;
      }

      //누적합
      for(int i=2;i<=S.length;i++){
         for(int j=0;j<26;j++){
            count[j][i] += count[j][i-1];
         }
      }

      //탐색
      int N = Integer.parseInt(in.readLine());
      StringTokenizer st;
      StringBuilder sb = new StringBuilder();
      int ch,l,r;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         ch = st.nextToken().charAt(0)-'a';
         l = Integer.parseInt(st.nextToken());
         r = Integer.parseInt(st.nextToken())+1;

         sb.append(count[ch][r]-count[ch][l]).append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과