[백준] 16139 인간-컴퓨터 상호작용 java 풀이

1. 문제 설명 📌

문제 링크

2. 접근 방식 🗃️

KEY WORD: 구간 합

누적합 배열 S에서 A~B 구간 내의 구간합을 구할 경우 어떻게 표현했는가?
S[B] - S[A-1] 이였다. A가 구간내에 합해지도록 A-1까지의 구간합을 제거했다. 이러한 원리는 구간 내에 알파벳이 몇 번 등장하는가 찾는 이번 문제에서도 사용할 수 있다.

위 그림과 같이, a가 A구간에서 한번, B구간에서 한번 나온다고 하자. 그러면, S[A] = 1, S[B] = 2가 될 것이다. 구간을 확인하면 문자열이 A의 위치를 넘어서서 B까지 구간을 정하는 순간 a는 한개이다. S[B]-S[A]는 A+1 ~ B까지의 구간합임으로 2-1 = 1이 나온다. 반면 S[B] - S[A-1]은 A의 위치부터 B까지의 거리에서 a의 개수임으로 S[B] - S[A-1] = 2- 0 = 2가 나온다.

우리는 위와 같은 누적합이 a부터 z까지 총 26개가 필요하다. 따라서 2차원 배열로 만들어서, 열은 알파벳, 행은 문자열의 위치별로 각 문자가 나온 횟수의 누적으로 생각한다.

다음은 문제에서 나온, seungjaehwang에 대한 2차원 배열이다.

	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
2	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
3	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
4	0	0	0	0	1	0	1	0	0	0	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
5	0	0	0	0	1	0	1	0	0	1	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
6	1	0	0	0	1	0	1	0	0	1	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
7	1	0	0	0	2	0	1	0	0	1	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
8	1	0	0	0	2	0	1	1	0	1	0	0	0	0	1	0	0	0	1	0	1	0	0	0	0	0
9	1	0	0	0	2	0	1	1	0	1	0	0	0	0	1	0	0	0	1	0	1	1	0	0	0	0
10	1	0	0	0	2	0	1	1	0	1	0	0	0	0	1	0	0	0	1	0	1	1	0	0	0	0
11	2	0	0	0	2	0	1	1	0	1	0	0	0	0	1	0	0	0	1	0	1	1	0	0	0	0
12	2	0	0	0	2	0	2	1	0	1	0	0	0	0	2	0	0	0	1	0	1	1	0	0	0	0

해당 배열을 완성했다면, 이후부터는 문제에서 원하는 알파벳과 구간에 맞게 누적합에서 구간합을 구하면 되므로, 이후 과정에 대한 풀이 설명은 생략하고 바로 코드 소개로 넘어가겠다.

3. 코드 소개 🔎

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

public class Main {
    /*
    * b16391 인간-컴퓨터 상호작용
    * 1. 알파벳을 행, 해당 알파벳이 나온 횟수 누적을 열로 표현
    * 2. 알파벳 a가 나온 횟수의 누적합 배열을 Sa라고 할때,
    * 3. Sa[B] - Sa[A-1]은 A ~ B까지의 a가 나온 횟수가 됨.
    *
    * ex)   만약 2-1이라면, a는 구간 전에 한번 등장했다는 뜻임.
    *       A-1번까지의 누적합 = 1 이란 소리임으로
     * */
    public static void main(String[] args) throws IOException {
        int [][] sum;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        sum = new int [26][s.length()+1];
        for (int i = 0; i < s.length(); i++) {
            int w = (int)s.charAt(i) - 97;
            for (int j = 0; j < 26; j++) {
                if(j == w)  sum[j][i+1] = sum[j][i] + 1;
                else        sum[j][i+1] = sum[j][i];
            }
        }

        int tc = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tc; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int w = (int)st.nextToken().charAt(0) - 97;
            int start   = Integer.parseInt(st.nextToken());
            int end     = Integer.parseInt(st.nextToken());
            sb.append(sum[w][end+1] - sum[w][start]).append("\n");
        }
        System.out.println(sb);
    }
}

4. 배운 것들 🎯

완전 탐색을 쓴다면, 문자열 최대 길이 \(10^5\) 답을 바라는 구간의 개수 \(10^5\) 이라서 최악의 경우 최대 \(10^{10}\)의 연산이 필요해서 시간 초과가 날 것이다.