백준[자바]_16139_인간컴퓨터상호작용_누적합_구간합

오늘은 백준 단계별로 문제풀기에서 누적합으로 분류된 문제를 풀이하겠다. 이전에 구간합에 대해 정리한 내용이 있어서 쉽게 풀리겠지 하고 생각을 했는데, 아니나 다를까 틀렸다. ㅜㅜ 한 가지 간과한 사실을 인지하고 코드를 수정해서 정답을 맞추었다. 처음에 생각했던 알고리즘 접근 과정과 간과했던 부분, 수정한 부분을 정리하고자 한다.

구간합에 대한 내용을 아직 잘 모른다면 여기를 눌러서 공부하고 오기를 바란다. 

 

[ 접근 과정 : 오류 있는 코드]

이 문제의 입력값의 최악의 경우를 보면 어마무시하다. 문자열의 길이는 최대값이 200,000, 최대 문제의 수도 200,000개, 구간의 최대 길이도 200,000이다. 이 문제를 단순히 반복문 만을 이용해서 풀이한다면 볼것도 없이 시간초과가 날것이다. 

그렇다면 시간 복잡도를 줄이기 위한 알고리즘이 필요한데 이 개념이 구간합이다. 그저 중첩 반복문을 이용해서 구간의 합을 구하게 되면 O(n^2)의 시간 복잡도가 필요하지만, 누적합을 미리 구해서 구간합 개념을 사용하게 되면 처음에 누적합을 구하는 시간복잡도 또한 O(n)으로 줄일수 있고, 특정 구간의 합을 구하는 시간복잡도는 O(1)로 첨자로 바로 접근이 가능하다. 

1. 누적합을 저장할 1차원 배열을 만든다. 
2. 문자열의 길이만큼 반복문을 돌면서 누적합을 구하는데, 문자열의 charAt(i)함수를 사용해 인덱스의 문자값이 문제에서 주어지는 특정 문자와 동일하다면 카운트를 증가시켜서 누적합 배열에 같은 인덱스에 카운트 값을 저장한다.   (dp[i] = ++cnt) 
3. 구간의 범위가 n ~ m이라고 할때, 시작인덱스 n이 0이 아니라면 
   1. 해당 구간의 구간합은 dp[m] - dp[n-1]이된다. 구간 인덱스의 경계값을 포함하기 때문에 n-1의값을 뺀다. 
4. 시작 인덱스 n이 0이라면 
   1. 위의 점화식을 그대로 적용하면 -1이 되어  ArrayIndexOutofBoundsException이 발생하기 때문에 이때는 그냥 dp[m]이 정답이다. 

여기까지가 처음에 풀었던 문제풀이 접근법이다. 문제가 없어보였지만, 필자가 간과한 것은 문제에서 주어지는 특정 문자가 모두 같지 않다는 것을 인지하지 못했다. 즉, 하나의 문자에 대해서만 구간합을 구한것이다. 

결론적으로 최악의 경우 20만개의 질문에서 특정 문자가 모두 같다는 보장은 없다. 따라서 누적합 배열을 2차원 배열로 만들어야 한다. 배열을 설명하자면 다음과 같다. 

dp[i][c] -> 0~i까지의 인덱스 중에서 특정문자 c의 개수를 저장한다.

 

알고리즘을 접근한 아이디어 자체는 오류가 없지만 문제를 제대로 이해하지 못했다. 위의 알고리즘을 그대로 적용하고 구간합 배열만 2차원으로 바꾸어주면 아래와 같은 소스코드를 구현할 수 있다. 이때 한 가지 고려해야 할 점은 dp배열은 int형이기 때문에 입력값을 문자로 받은 후, 해당 문자의 아스키코드 값에서 a의 아스키 코드 값을 빼준 값을 저장한다. 모든 알파벳 소문자의 아스키코드는 a보다 작거나 같기 때문이다. 

주석에 자세한 내용을 달아두었으니 참고하면 좋을듯 하다.

package Main;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class _16139_누적합_인간컴퓨터 {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        String question = br.readLine();
        
        
        //누적합 배열을 만들자
        //dp[n][a] -> 0~n까지의 범위중에서 특정 문자 a의 개수를 저장한다. a에는 특정 문자의 아스키코드값에서 'a'를 뺀값을 저장한다.
        //2~5까지의 범위가 주어진다면 
        //dp[5][a] - dp[1][a]이다. 
        //모든 알파벳의 수는 26개이다. a-z
        int dp[][] = new int[question.length()][26];
        
        
        //문자열은 변하지 않기 때문에 
        //해당 문자열의 특정 구간에서 특정 문자가 몇개가 있는지를 각각 저장하면 된다.!
        //문자열을 한 번만 O(n)으로 탐색하면서 특정 문자열이 등장했을때 해당 문자열의 아스키코드값에 해당하는 번지수에 이전값+1을 누적해서 더한다. 
        //특정문자가 연속되면 값이 1,2,3 이런식으로 되겠지만 웬만하면 0이 반복될 것이다. 
        
        //초깃값 초기화. 모든 알파벳 소문자는 'a'보다 크거나 같으니 인덱스가 음수가 될 일은없음
        dp[0][question.charAt(0)-'a']++;
        
        //초깃값을 제외한 다음 문자부터 값을 저장한다.
        for(int i=1; i<question.length(); i++) {
            int tmp = question.charAt(i)-'a';
            
            for(int j=0; j<26; j++) {
                dp[i][j] = dp[i-1][j]; 
                //해당 문자열에 대해 이전값을 누적한다. 지금은 tmp라는 문자에대해서만 cnt를 증가시켰다.
                //하지만 예를 들어 이전 문자는 tmp가 아닌 다른 값의 누적합을 더했을 수도 있기 때문에, 
                //값을 옮겨주지 않으면 그 이후에는 0이 누적되어 올바르지 않은 결과가 도출된다. 
                /*
                    ex 2번째 문자가 a여서 dp[1][a]++해주었다. 
                       3번째 문자가 b여서 dp[2][b]++해주었다.  
                       4번째 문자가 a여서 dp[3][a]++해주었다.
                    위와 같은 상황이 있을때, a는 2번째에서 가장 처음 나왔다고 가정을 해보자 
                    dp[1][a] = 1일것이다. 
                    그런데 이때, 39행의 명령을 수행해주지 않으면 dp[2][a]는 초기화를 해주지 않았기 때문에 0이다. 
                    그래서 다시 한 번 a가 나온 경우 dp[3][a]는 2가되는 것이 맞지만, 1이 되어버린다.
                 */            
            }
            
            dp[i][tmp]++; //특정 문자열의 등장 횟수르 증가시킨다.
        }
        
        
        
        
        int t = Integer.parseInt(br.readLine());
        
        for(int k=0; k<t; k++) {
            st = new StringTokenizer(br.readLine());
            
            char find = st.nextToken().charAt(0);
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            
                
            
            if(start == 0) {
                sb.append(dp[end][find-'a']).append('\n');
            }else {
                sb.append(dp[end][find-'a'] - dp[start-1][find-'a']).append('\n');
            }
            
        }
        
        System.out.println(sb);
    }
 
}