[백준 16439번] 인간-컴퓨터 상호작용 (Java)

누적합을 적응하기 위해

도전한 문제!

 

아무 생각 없이 풀었을 때는 50점 나왔는데,

공책에 적으면서 푸니까 맞았다.

 

집중하는 것이 중요한 것 같다!

 

---

문제

 

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

 

 

---

풀이

 

알고리즘 설계 [접근 방법] : 누적합 + dp

알파벳이 주어지고, 처음과 시작 구간을 매번 입력받을 때마다 조회한다면 20000*20000이 되어 시간초과가 발생한다.

그래서 질문이 주어졌을 때 반복문을 실행하지 않는 방법을 고민했다.

시작구간과 끝구간에서 알파벳이 누적으로 몇 번 사용되었는지 알면 끝부분 누적 - 시작부분 누적으로 바로 계산이 가능하다.  

 

풀이 과정

1.

문자열을 입력받는다.

 

2.

알파벳 26개마다 누적합을 계산해야 하므로 dp[26][문자열의 길이+1]의 dp배열을 생성한다.

 

3.

현재 문자열의 문자를 인덱스로 생각하고, 그 것에 맞는 배열의 값을 +1해준다.

만약 현재의 값이 a라면 dp[0][현재 문자열 인덱스+1]값을 dp[0][현재 문자열 인덱스]+1해준다.

 

4.

질문의 개수를 입력받고, 시작 부분과 끝 부분을 입력받는다.

문자를 입력받으면 배열에서 그 문자의 끝부분 - 시작부분을 계산하여 StringBuilder에 담는다.

 

5.

StringBuilder를 출력한다.

 

주의할 점

값을 입력받을 때, Scanner를 사용하면 시간초과가 발생하여 50점이 된다.

 

---

코드

 

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

public class Test_16139_인간컴퓨터상호작용 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] word = br.readLine().toCharArray();
		
        	//누적합
		int[][] dp = new int[26][word.length+1];
		for(int i=0; i<word.length; i++) {
			
			int idx = word[i]-'a';
			
			for(int j=0; j<dp.length; j++) {
				if(j==idx) dp[j][i+1]= dp[j][i]+1;
				else dp[j][i+1]= dp[j][i];
			}
		}

		StringBuilder sb = new StringBuilder();
		int test = Integer.parseInt(br.readLine());
		for(int t=0; t<test; t++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str); 
			
			char ch = st.nextToken().charAt(0);
			
			int start = Integer.parseInt(st.nextToken())+1;
			int end = Integer.parseInt(st.nextToken())+1;
			
			int idx = ch-'a';
			sb.append((dp[idx][end]-dp[idx][start-1])+ "\n");
		}
		
        	//출력
		System.out.println(sb.toString());
	}
}

 

 

 

(❁´◡`❁)

끝!