백준 16139 인간-컴퓨터 상호작용 Java: 문자별 누적합

백준 16139번 ‘인간-컴퓨터 상호작용’은 문자열의 구간 [left, right]에 특정 알파벳이 몇 번 등장하는지 여러 번 묻는다. 매 query마다 구간을 다시 세면 최악 O(NQ)이므로, 알파벳별 누적 등장 횟수를 먼저 만든다.

• 백준 16139번 인간-컴퓨터 상호작용

prefix index를 한 칸 밀어 두기

prefix[c][i]를 문자열의 앞 i개 문자에 알파벳 c가 등장한 횟수라고 정의한다.

prefix[c][0] = 0
prefix[c][i + 1] = s[0..i]에서 c의 개수

문제의 query index는 0부터 시작하고 양끝을 모두 포함한다. 그러면 [left, right]의 답은 다음 한 줄이다.

prefix[c][right + 1] - prefix[c][left]

right + 1이 들어가는 이유는 prefix의 두 번째 index가 원본 문자열 index가 아니라 문자 개수이기 때문이다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int ALPHABET_COUNT = 26;

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );

        String text = reader.readLine();
        int[][] prefix = new int[ALPHABET_COUNT][text.length() + 1];

        for (int index = 0; index < text.length(); index++) {
            for (int alphabet = 0; alphabet < ALPHABET_COUNT; alphabet++) {
                prefix[alphabet][index + 1] = prefix[alphabet][index];
            }

            int current = text.charAt(index) - 'a';
            prefix[current][index + 1]++;
        }

        int queryCount = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int query = 0; query < queryCount; query++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            int alphabet = tokenizer.nextToken().charAt(0) - 'a';
            int left = Integer.parseInt(tokenizer.nextToken());
            int right = Integer.parseInt(tokenizer.nextToken());

            int count = prefix[alphabet][right + 1]
                    - prefix[alphabet][left];
            output.append(count).append('\n');
        }

        System.out.print(output);
    }
}

왜 26개를 매번 복사하나

각 index의 prefix는 직전 index의 26개 count를 이어받아야 한다. 현재 문자 하나만 증가시키되 나머지 알파벳의 이전 count도 보존해야 하므로 26칸을 복사한다.

문자열 길이를 N, query 수를 Q라 하면 다음과 같다.

• 전처리: O(26N), 알파벳 수가 고정이므로 O(N)으로 볼 수 있음
• query: 건당 O(1), 전체 O(Q)
• 공간: O(26N)

특정 문자별 등장 index 목록을 저장하고 binary search로 query를 처리하는 대안도 있다. 이 문제의 lowercase alphabet 26개와 최대 입력에서는 prefix table이 단순하고 충분하다.

0-based index에서 한 번 틀린 기록

원문에는 누적합 아이디어는 바로 잡았지만 문제 index가 0부터 시작한다는 점 때문에 첫 제출에서 틀렸고, 곧바로 고쳐 통과했다고 적혀 있다. N+1 prefix를 쓰면 왼쪽 끝이 0인 query도 별도 분기 없이 처리할 수 있다.

당시에는 점심시간 30~40분에 알고리즘 문제를 푸는 것이 가장 효율적인 것 같다는 짧은 메모도 남겼다. 그 생활 판단을 일반화할 수는 없지만, 짧은 시간에도 상태 정의와 index convention을 먼저 적어 두는 습관은 off-by-one 오류를 줄이는 데 직접 도움이 된다.

고정 길이 수열 구간 합은 백준 2559 수열, 2차원 사각형 구간 합은 백준 11660 구간 합 구하기 5에서 이어진다.

검증 범위

Java source를 수동 검토하고 한 글자 문자열, left = 0, right = N - 1, 존재하지 않는 문자와 작은 random 문자열 query를 직접 count하는 oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.