[JAVA] 백준 16139 구간합

 

 

 

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

문제

승재를 도와 특정 문자열 $S$ 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$ 이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라.

풀이

문자열이 주어졌을 때, 특정 알파벳에 대한 개수의 구간합을 구하는 프로그램이었다.

먼저 문자열에 대한 알파벳에 대한 구간합을 먼저 구하고 알파벳과 구간이 주어졌을 때 출력해주었다.

📌 알파벳에 대한 구간합 구하기

        String target = br.readLine();

        int[][] A = new int[target.length()+1][26];

        for(int i=1; i<target.length()+1; i++){
            int value = target.charAt(i-1) - 'a';
            for(int j=0; j<A[i].length; j++){
                A[i][j] = A[i-1][j] + (value == j ? 1 : 0);
            }
        }

• 주어진 문자열 + 1 길이와 알파벳마다 구간합을 다르게 만들기 위해 26 길이의 2차원 배열을 만들었다.
• 문자열을 한글자씩 - ‘a’연산을 통해 인덱스를 구해주고 구간합을 구했다.

📌 출력

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine() , " ");
            int value = st.nextToken().charAt(0) - 'a';
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(A[b+1][value] - A[a][value]).append("\n");
        }
        System.out.println(sb);

• 알파벳 value와 구간 a, b가 주어졌을 때, 구간합은 A[b + 1][value] - A[a][value]를 구하면 구간합을 구할 수 있다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));

        String target = br.readLine();

        int[][] A = new int[target.length()+1][26];

        for(int i=1; i<target.length()+1; i++){
            int value = target.charAt(i-1) - 'a';
            for(int j=0; j<A[i].length; j++){
                A[i][j] = A[i-1][j] + (value == j ? 1 : 0);
            }
        }

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine() , " ");
            int value = st.nextToken().charAt(0) - 'a';
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(A[b+1][value] - A[a][value]).append("\n");
        }
        System.out.println(sb);

    }
}

결과