[백준] 11441 인간-컴퓨터 상호작용 - 누적합(Prefix Sum) + DP + 알파벳(문자열) JAVA

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

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

코드설명

누적합과 알파벳을 사용한 문제입니다.

조금 넓게본다면, DP와도 연관이 있습니다.

 

문제 로직입니다.

seungjaehwang
4
a 0 5
a 0 6
a 6 10
a 7 10

1. 누적합을 진행하기 위해 prefixSum[s.length() + 1][26] 을 선언합니다. (prefixSum[0][26]은 모두 0으로 처리하기 위해 prefixSum[s.length() + 1][26]으로 처리합니다.)
2. prefixSum에서 숫자를 통해 누적합을 구하듯, 알파벳도 같이 진행합니다.
   
   1. prefixSum[1][0~26] = prefixSum[0][0~26] 로직을 통해 0번째 문자열에서 가지고 있는 문자알파벳의 개수를 모두 가져옵니다. ( prefixSum[0][26] 모두 0 입니다. )
   2. prefixSum[1][s - 'a'] += 1; 을 통해 새로 추가된 문자열 알파벳의 개수를 증가시켜줍니다.
3. 0번쨰 문자열 IDX를 처리했다면 이제 1번쨰 문자열 Idx를 누적합진행합니다.( prefixSum 입장에서는 prefixSum[1][26]이 모두 처리가 끝났고, prefixSum[2][26]을 처리한다는 의미입니다. 문자열과 prefixSum Index의 값이 일치하지 않으니 유의하시기 바랍니다. )
   1. prefixSum[2][0~26] = prefixSum[1][0~26] 로직을 통해 문자열에서 0번째 Idx까지 가지고 있는 문자알파벳의 개수를 모두 가져옵니다.
   2. prefixSum[2][e - 'a'] += 1; 을 통해 새로 추가된 문자열 알파벳의 개수를 증가시켜줍니다.
4. 위의 로직들을 통해 각 문자열마다 각 인덱스마다 각 인덱스까지 나온 모든 알파벳의 개수를 알고 있습니다.
5. 이제 질문이 들어왔을때, 만약 a 0 5 가 들어왔다면, prefixSum[6][26] - prefixSum[0][26] 을 통해 0 ~ 5까지의 누적합을 구할 수 있습니다. 여기서 prefixSum[6][26]인 이유는 prefixSUm[6]이 문자열 알파벳 5까지의 알파벳의 개수를 가지고 있습니다.

 

 

코드

prefixSum[S.length() + 1][0~26]로 처리하는 코드

이럴경우 질문에서 Index가 0부터 시작하므로 endIdx+ 1 처리합니다.

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

public class Main {
	public static int q;
	public static String S;
	public static int[][] prefixSum;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	

    	S = st.nextToken();
    	prefixSum = new int[S.length()+1][26];
    	
    	//나머지 문자탐색
    	for(int i=0; i<S.length(); i++) {
    		//탐색 중인 문자
    		int alphabetidx= S.charAt(i)-'a';
    		for(int j=0;j<26;j++) {
    			prefixSum[i+1][j] = prefixSum[i][j];
    		}
    		prefixSum[i+1][alphabetidx] += 1;
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	q = Integer.parseInt(st.nextToken());
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=0;i<q;i++) {
    		st = new StringTokenizer(br.readLine());
    		char targetAlphabet = st.nextToken().charAt(0);
    		int startIdx = Integer.parseInt(st.nextToken());
    		int endIdx = Integer.parseInt(st.nextToken());
    		
    		sb.append(prefixSum[endIdx+1][targetAlphabet -'a'] - prefixSum[startIdx][targetAlphabet -'a']).append('\n');
    	}
    	System.out.println(sb);
    }
}

 

prefixSum[S.length()][0~26]로 처리하는 코드

 

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

public class Main {
	public static int q;
	public static String S;
	public static int[][] prefixSum;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	

    	S = st.nextToken();
    	prefixSum = new int[S.length()][26];
    	
    	prefixSum[0][S.charAt(0)-'a']+=1; //첫번째는 먼저 선언해주어야 이후의 누적합을 저장가능합니다.
    	
    	//나머지 문자탐색
    	for(int i=1; i<S.length(); i++) {
    		//탐색 중인 문자
    		int alphabetidx= S.charAt(i)-'a';
    		for(int j=0;j<26;j++) {
    			prefixSum[i][j] = prefixSum[i - 1][j];
    		}
    		prefixSum[i][alphabetidx] += 1;
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	q = Integer.parseInt(st.nextToken());
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=0;i<q;i++) {
    		st = new StringTokenizer(br.readLine());
    		char targetAlphabet = st.nextToken().charAt(0);
    		int startIdx = Integer.parseInt(st.nextToken());
    		int endIdx = Integer.parseInt(st.nextToken());
    		
    		if(startIdx == 0) {
    			sb.append(prefixSum[endIdx][targetAlphabet - 'a']).append('\n');
    		}else {
    			sb.append(prefixSum[endIdx][targetAlphabet -'a'] - prefixSum[startIdx-1][targetAlphabet -'a']).append('\n');
    		}
    	}
    	System.out.println(sb);
    }
}