[백준] 16139. 인간-컴퓨터 상호작용 (자바 JAVA)
문제
승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.
'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'
승재를 도와 특정 문자열 $ S\mathit{} $, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $ S\mathit{} $의 $ l\mathit{} $번째 문자부터 $ r\mathit{} $번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $ l\mathit{} $번째와 $ r\mathit{} $번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $ q\mathit{} $번 할 것이다.
입력
첫 줄에 문자열 S가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $ q\mathit{} $가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 줄부터 $ q+2\mathit{} $번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 $\alpha_i$와 $0\leq l_i\leq r_i<|S|$를 만족하는 정수 $ l_i\mathit{}, r_i\mathit{} $가 공백으로 구분되어 주어진다.
출력
각 질문마다 줄을 구분해 순서대로 답변한다. $ i\mathit{} $번째 줄에 $ S $의 $ l_i\mathit{} $번째 문자부터 $ r_i\mathit{} $번째 문자 사이에 $ \alpha_i $가 나타나는 횟수를 출력한다.
서브태스크 1 (50점)
문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.
서브태스크 2 (50점)
추가 제한 조건이 없다.
예제 입력 1
seungjaehwang
4
a 0 5
a 0 6
a 6 10
a 7 10
예제 출력 1
0
1
2
1
1차 시도
가장 먼저 생각했던 접근법은 S의 l번째 문자부터 r번째 인덱스 사이의 문자가 α와 같은지 확인하고 개수를 세는 것이었고 다음과 같이 풀이했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
long q = Integer.parseInt(br.readLine());
while (q-- > 0) {
int count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
char alpha = st.nextToken().charAt(0);
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
for (int i = l; i <= r; i++) {
char ch = S.charAt(i);
if (ch == alpha) {
count++;
}
}
System.out.println(count);
}
}
}
하지만 50점이 나오고야 말았다..
문제 접근법
문자열의 길이 𝑆 ≤ 200,000, 쿼리의 개수 𝑞 ≤ 200,000 이므로,
총 연산 횟수는 200,000×200,000=40,000,000,000가 되어 1초에 1억 번의 연산을 처리할 수 있는 기준을 크게 초과한다.
따라서, 단순 for문 접근으로는 시간 초과가 발생한다.
범위 [l, r]에서 인덱스 문자가 α와 같은지 확인해야 하므로, 누적합으로 풀면 된다.
100점 풀이
문자열 S의 각 문자에 대해, 현재까지의 알파벳 등장 횟수를 계산해서 sums 배열에 저장한다.
이 때 sums[i][j]는 S의 1번째 문자부터 i번째 문자까지 알파벳 j (즉, 'a' + j)가 등장한 누적 횟수.
예를 들어, sums[3][0]은 문자열의 1번째 문자부터 3번째 문자까지 'a'가 등장한 횟수를 의미한다.
j번째 알파벳에 대해 이전 값 sums[i - 1][j]를 복사하고, j가 현재 알파벳 alpha와 같으면 +1을 추가한다.
예를 들어 S = "abac"일 때
첫번째 문자 a를 탐색할 때 sums[0] = 1이 되고,
두번째 문자 b를 탐색할 때 sums[1] = 1이 되고,
세번째 문자 a를 탐색할 때 sums[0] = 2이 되고,
네번째 문자 c를 탐색할 때 sums[2] = 1이 되는 식으로...
| $i$ | 문자 $S[i-1]$ | $sums[i]$ (a, b, c, ...) |
| 0 | - | [0, 0, 0, ..., 0] |
| 1 | 'a' | [1, 0, 0, ..., 0] |
| 2 | 'b' | [1, 1, 0, ..., 0] |
| 3 | 'a' | [2, 1, 0, ..., 0] |
| 4 | 'c' | [2, 1, 1, ..., 0] |
이 연산을 수행하는데 시간복잡도는 O(N×26)을 해서 O(26N)이 되고,
영어 알파벳의 개수(26)는 상수이므로 최종 시간 복잡도는 O(N)이 된다.
이렇게 해서 구한 누적합 배열로 구간의 합을 구했더니 100점이 나왔다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String S = br.readLine();
int[][] sums = new int[S.length() + 1][26];
for (int i = 1; i < S.length() + 1; i++) {
int alpha = S.charAt(i - 1) - 'a'; // i번째 문자의 알파벳 인덱스
for (int j = 0; j < sums[i].length; j++) {
sums[i][j] = sums[i - 1][j] + (alpha == j ? 1 : 0);
}
}
int q = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int alphaIndex = st.nextToken().charAt(0) - 'a';
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
sb.append(sums[r + 1][alphaIndex] - sums[l][alphaIndex]).append("\n"); // 문자열의 1번째 문자부터 r번째 문자까지의 누적합
}
System.out.println(sb);
}
}
후기
배열이 변하지 않으니 구간의 합도 변하지 않는다는 점을 바탕으로 앞에서부터 차례대로 누적된 합을 구하고 이걸 이용해서 구간의 합을 구하면 효율성이 올라간다.