[백준] 16139 : 인간-컴퓨터 상호작용 (JAVA)

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

📌 50점,,

16139번 문제는 다음과 같은 조건에 따라 점수가 부여되는 문제였습니다. 

서브태스크 1 (50점)
문제열의 길이는 2000자 이하, 질문의 수는 2000개 이하이다.

서브태스크 2 (50점)
추가 제한 조건이 없다.

 

문제를 보고 간단히 구현해 풀었으나, 50점만 받았습니다..🥲

 

50점 받은 코드입니다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        char[] chArr = br.readLine().toCharArray();

        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int answer = 0;
            char ch = st.nextToken().charAt(0);
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            for (int j = s; j <= e; j++) {
                if (ch == chArr[j]) {
                    answer++;
                }
            }

            sb.append(answer + "\n");
        }

        bw.write(sb.toString() + "");
        bw.close();
    }
}

 

🚩 누적 합

50점 코드를 작성하고 나서 다른 분들의 풀이를 확인해 보니 2차원배열을 사용해 모든 알파벳을 기준으로 누적합을 계산하는 방식으로 푼 것을 확인할 수 있었습니다!

 

 

누적합 구현을 구체적으로 설명하자면, 주어진 문자열과 알파벳 데이터를 기반으로 2차원 배열을 생성하고, 문자열을 순회하며 각 알파벳이 포함되었는지를 확인해 누적합 방식으로 값을 저장합니다.

 

 

누적합 계산이 완료되면, 주어진 범위 내에 찾고자 하는 문자가 몇 개 포함되어 있는지를 end - (start-1) 연산을 통해 쉽게 구할 수 있습니다.

 

100점 받은 코드입니다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        char[] arr = br.readLine().toCharArray();     // 주어진 문자열을 char 배열로 바로 변환

        int[][] check = new int[arr.length][26];
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i] - 'a';

            for (int j = 0; j < 26; j++) {      // 누적합
                if (i != 0) check[i][j] += check[i - 1][j];
                if (j == num) check[i][j] += 1;
            }
        }

        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int num = st.nextToken().charAt(0) - 'a';
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            if (s == 0) {
                bw.write(check[e][num] + "\n");
            } else {
                bw.write(check[e][num] - check[s - 1][num] + "\n");
            }
        }

        bw.close();
    }
}