[BOJ/JAVA] 백준 16139 : 인간-컴퓨터 상호작용 (자바)

문제 정보

  문제명   - 인간-컴퓨터 상호작용
  난이도   - 실버 I
문제 번호 - 16139번

---

문제 링크

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

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

---

문제

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. 
'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'
승재를 도와 특정 문자열 S, 특정 알파벳 alpha와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 alpha가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다. 

---

입력

첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 
q가 주어지며, 문제의 수는 1≤q≤200,000을 만족한다. 세 번째 줄부터 (q+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 alpha_i와 0\leq l_i\leq r_i<|S|를 만족하는 정수 l_i,r_i가 공백으로 구분되어 주어진다.

---

출력

각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 l_i번째 문자부터 r_i번째 문자 사이에 alpha_i가 나타나는 횟수를 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
seungjaehwang 4 a 0 5 a 0 6 a 6 10 a 7 10	0 1 2 1

---

알고리즘 분류

● 누적 합

---

소스코드

package Lv2_Silver;

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

/**
 * @author HanHoon
 * @category 누적 합
 * https://www.acmicpc.net/problem/16139
 */
public class BOJ_S1_16139_인간_컴퓨터_상호작용 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder str = new StringBuilder();

        // S: 특정 문자열
        String S = br.readLine();
        // q: 질문의 수
        int q = Integer.parseInt(br.readLine());

        // 누적합 기록 배열
        int[][] dp = new int[S.length()+1]['z'-'a'+1];
        // 누적 합 계산
        for(int i = 1; i <= S.length(); i++){
            int cnt = dp[i-1][S.charAt(i-1)-'a'] + 1;
            // 문자열 S의 길이는 200,000자 이하이므로 열마다 값을 초기화 하는 것 보다, 각 행마다 돌려주는 것이 유리하다.
            for (int n = 0; n < 'z'-'a'+1; n++)
                dp[i][n] = n == S.charAt(i-1)-'a' ? dp[i-1][n]+1 : dp[i-1][n];
        }

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

            str.append(dp[r+1][alpa-'a'] - dp[l][alpa-'a']).append("\n");
        }
        System.out.print(str);
        br.close();
    }
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---