[Algorithm] 백준 누적합 문제 - 인간-컴퓨터 상호작용(16139) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 누적합 문제 - 인간 컴퓨터 상호작용 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/16139

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

 

1. 풀이 소스

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Question> qs = new ArrayList<>(); // question을 저장할 리스트
        
        String str = br.readLine();
        int n = str.length();
        int q = parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            qs.add(new Question(st.nextToken().charAt(0), parseInt(st.nextToken()), parseInt(st.nextToken())));
        }
        
        int[][] dp = new int[n + 1][26]; // dp 2차원 배열 (누적합)

        for (int i = 1; i <= n; i++) { // 인덱스 에러를 방지하기 위해 1부터 시작
            int num = str.charAt(i - 1) - 'a'; // char - 'a'로 정수로 변환
            for (int j = 0; j < 26; j++) {
                if (j == num) dp[i][num] = dp[i - 1][num] + 1; // 만약 해당 문자에 해당하는 정수라면 +1
                else dp[i][j] = dp[i - 1][j]; // 아니라면 그대로
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Question question : qs) {
            int num = question.c - 'a';
            sb.append(dp[question.e][num] - dp[question.s][num]).append("\n"); //양 끝을 포함해야하므로 e는 1을 더해주고, s는 그대로
        }
        
        System.out.print(sb);
    }
    
    static class Question {
        char c;
        int s;
        int e;
        
        Question (char c, int s, int e) {
            this.c = c;
            this.s = s;
            this.e = e + 1; // 끝점 포함 
        }
    }
}

 

2. 풀이 중점 사항

 

문제 해결 방법은 문자열 길이 n를 탐색하며 26개의 알파벳을 누적합으로 업데이트하는 방법입니다.

시간 복잡도는 O(n * 26 + question.size()) 으로 계산할 수 있습니다. 시간제한이 1초이므로 n, quesion.size()가 최대 20만이므로 약 O(540만)입니다. 1초에 약 1억 번 연산이 가능하므로 문제를 해결할 수 있을 것이라고 판단하였습니다.

 

for (int i = 1; i <= n; i++) { // 인덱스 에러를 방지하기 위해 1부터 시작
    int num = str.charAt(i - 1) - 'a'; // char - 'a'로 정수로 변환
    for (int j = 0; j < 26; j++) {
        if (j == num) dp[i][num] = dp[i - 1][num] + 1; // 만약 해당 문자에 해당하는 정수라면 +1
        else dp[i][j] = dp[i - 1][j]; // 아니라면 그대로
    }
}

 

26개의 문자를 배열에 저장하기 위해 char - 'a'를 하여 0 ~ 26의 정수형을 만들었습니다.

이후, num의 값을 가지는 2차원 배열은 +1을 하고 나머지는 그대로 유지하도록 설정하였습니다.