16139번

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

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

처음 이 문제를 봤을 때는 그냥 주어진 문자열과 주어진 시작,끝 인덱스를 이용해서 비교값과 같으면 count값을 증가시키는 방식을 생각해냈다.

하지만 그렇게 했더니 50점만 받을 수 있었다. 이 문제에서 바라는 것은 누적합계산이었다. 즉, 값 저장 배열을 만들어서 누적된 계산의 합을 구하라는 것이다.

그래서 표를 만들었다. joon이라는 문자열이 주어졌다고 가정 했을 때 표를 채워보면, 행의 길이는 주어진 문자열의 길이이고, 열은 알파벳 26자리 이다.

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

0

1

1

1

2

2

3

1

위의 표처럼 joon에 대해서 순서대로 j는 j의 칸의 값을 증가 시키고 o는 o의 칸을 증가시킨다. 그리고 n도 마찬가지로 한다.

그럼 이 방식을 사용해서 코드를 짠다면 주어진 끝지점 인덱스에서 시작지점 인덱스-1지점을 빼면 시작지점과 끝지점 사이에 있는 누적 알파벳의 수가 나온다. 위 표를 예로들어 o 1 2라고 주어진다면 2-0으로 2가 나온다.

 

정답 코드는 아래와 같다.

 

package backjoon;

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

public class b16139 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = br.readLine();
        int test = Integer.parseInt(br.readLine());
        int[][] alpha = new int[target.length()][26];

        alpha[0][target.charAt(0)-'a']++;//for문을 0으로 시작할 수 없어서 초기화해준다.
		//0으로 시작하면 인덱스 exception이 발생한다.
        for(int i=1;i<target.length();i++){
            int tmp = target.charAt(i)-'a';
            for(int j=0; j<26; j++){
                alpha[i][j]=alpha[i-1][j];//이전 행에서 추가한 값을 복사해온다.
            }
            alpha[i][tmp]++;//새로 누적되는 값을 증가시킨다.
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<test; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            char comp=st.nextToken().charAt(0);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            if(start==0){
                sb.append(alpha[end][comp-'a']).append("\n");
            }//시작지점이 0일때는 끝지점의 값이 누적 값이다.
            else sb.append(alpha[end][comp-'a']-alpha[start-1][comp-'a']).append("\n");
        }//끝지점에서 시작지점-1지점을 빼는 것은 시작지점 또한 누적 값에 포함하기 위해서이다.
        System.out.println(sb);
    }
}