[BOJ] 16139. 인간-컴퓨터 상호작용 - JAVA

🔗 문제

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

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

 

💻 풀이 및 코드

문제 유형 : 누적합

 

풀이

모든 알파벳에 대해서 그 알파벳이 몇 번 나왔는지 저장하면 된다.

0번 idex 에서 배열의 범위를 벗어나는 것을 방지하려고 문자열의 길이 + 1 을 크기로 하는 배열을 선언했다.

prefixSum[i][j] 는 i 번째 문자열까지 알파벳 j (a ~ z ) 가 몇 번 나왔는지 기록한다.

 

느낀 점

왜 이런 생각을 못할까...

 

전체 코드

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

public class Main_bj_16139_인간컴퓨터상호작용 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_16139.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		int[][] prefixSum = new int[s.length()+1][26];	//i 인덱스의 알파벳 갯수 누적합 계산

		for(int i=1; i<=s.length(); i++) {
			for(int j=0; j<26; j++) {
				prefixSum[i][j] = prefixSum[i-1][j];
			}
			
			int idx = s.charAt(i-1)-'a';
			prefixSum[i][idx]++;
		}
		
		int Q = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int key = st.nextToken().charAt(0) - 'a';
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			sb.append(prefixSum[end+1][key] - prefixSum[start][key]).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}

}

---

Reference

https://code-master-s.tistory.com/147

[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java)