[백준] 16139번: 인간-컴퓨터 상호작용 Java

문제

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다.

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

승재를 도와 특정 문자열 S, 특정 알파벳 α와 문자열의 구간 [l,r]이 주어지면 S의 l번째 문자부터 r번째 문자 사이에 α가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 0번째부터 세며, l번째와 r번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 q번 할 것이다.

 

입력

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

 

출력

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

 

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

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

접근

질문할 때마다 매번 문자열을 탐색한다면 오랜 시간이 걸리므로, 누적합을 이용하여 구간개수를 계산합니다.

한 문자를 탐색할 때마다 알파벳 26문자에 대해 현재 탐색하고 있는 문자까지 누적 횟수를 기록합니다.

 

ex) cacao 에 대한 누적합 배열

		c	a	c	a	o
0 (a)	0	0	1	1	2	2
1 (b)	0	0	0	0	0	0
2 (c)	0	1	1	2	2	2
...	...	...	...	...	...	...
14 (o)	0	0	0	0	0	1
...	...	...	...	...	...	...
25 (z)	0	0	0	0	0	0

 

질문은 문자, 구간 시작, 구간 끝 형태로 들어오고, 구간 시작과 구간 끝을 포함한 개수를 물어봄으로

문자[구간 끝]의 누적합 - 문자[구간 시작 -1]의 누적합 을 계산하여 구간 개수를 구합니다.

구현

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String s = br.readLine(); //문자열
		int q = Integer.parseInt(br.readLine()); //질문 수
		int l=s.length();
		
		//누적합 기록을 위한 배열 선언
		int[][] memos = new int[l+1][26];
		//처음 값 횟수 증가
		memos[1][s.charAt(0)-'a']++;
		//나머지 문자 탐색
		for(int i=2;i<=l;i++) {
			//탐색 중인 문자
			int idx = s.charAt(i-1)-'a';
			//알파벳(a-z)탐색
			for(int j=0;j<26;j++) {
				//알파벳의 이전 누적 합
				int before = memos[i-1][j];
				//알파벳과 탐색 중인 문자가 같으면 이전값+1, 아니면 이전값과 같음
				memos[i][j]=j==idx?before+1:before;
			}
		}
		//문제 읽기
		StringTokenizer st;
		for(int i=0;i<q;i++) {
			st=new StringTokenizer(br.readLine());
			//문제 문자
			int idx=st.nextToken().charAt(0)-'a';
			//시작점
			int start=Integer.parseInt(st.nextToken())+1;
			//끝점
			int end=Integer.parseInt(st.nextToken())+1;
			//끝점의 누적합 - 시작점 바로 이전의 누적합 = 구간의 문자 반복값
			bw.append((memos[end][idx]-memos[start-1][idx])+"\n");
		}
		bw.close();
		br.close();
	}
}