알파벳 개수

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

출력

단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.

예제 입력 1

baekjoon

예제 출력 1

1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0

해결

출력 순서가 a부터 z까지 고정되어 있으므로 문자마다 빈 칸을 찾는 대신 길이 26인 배열을 만든다. 입력이 소문자로만 이루어졌다는 조건 덕분에 ch - 'a'가 0부터 25 사이의 인덱스가 된다. 한 글자를 읽을 때 해당 칸만 1 증가시키고, 끝나면 배열을 처음부터 출력한다.

왜 이 매핑이 가능한지 문자 코드로 확인해 보자. Java에서 'a', 'b', …, 'z'는 연속된 코드 값을 갖는다. 그래서 'a'-'a'=0, 'b'-'a'=1, 'z'-'a'=25가 된다. 입력 조건이 대문자나 한글을 허용했다면 이 식을 그대로 배열 인덱스로 써서는 안 된다. 문제에서 주어진 입력 범위를 알고리즘의 전제로 사용한 셈이다.

baekjoon을 따라가면 b에서 1번 칸, a에서 0번 칸이 1이 된다. o를 두 번 읽은 뒤에는 14번 칸이 2가 된다. 등장하지 않은 c의 칸은 초기값 0 그대로다. 이 예로 “개수”를 세는 문제와 다음 글의 “첫 위치”를 저장하는 문제를 구별할 수 있다.

작은 입력 abaca로 상태를 따라가면 동작이 더 분명하다.

읽은 글자	`a` 칸	`b` 칸	`c` 칸	바뀐 위치
시작	0	0	0	없음
`a`	1	0	0	0번
`b`	1	1	0	1번
`a`	2	1	0	0번
`c`, `a`	3	1	1	2번, 0번

각 단계에서 지금까지 읽은 부분 문자열에 나타난 각 문자의 횟수가 배열에 저장된다는 불변식이 유지된다. 한 글자마다 해당 칸 하나를 늘리므로 성립하고, 끝까지 읽으면 배열이 곧 답이다. 전체 출력에서는 이 세 칸 뒤에 d부터 z까지의 0도 순서대로 적는다.

문자열 길이를 L이라 하면 순회 O(L), 26칸 출력 O(26)으로 시간 O(L+26), 추가 공간 O(26)이다. 한 글자만 있어도 나머지 25칸을 0으로 출력해야 한다. 코드의 int[]가 0으로 초기화되는 점을 활용한다.

코드에서 result[ch - 'a']++가 셈을 수행하고, 마지막 반복문은 배열의 인덱스 순서가 곧 알파벳 순서이므로 정렬 없이 출력한다. 예제의 o처럼 중복 문자는 이미 기록된 칸을 덮어쓰지 않고 누적해야 한다. String.contains를 26번 호출해도 이 입력 크기에서는 통과할 수 있지만, 각 문자를 한 번 읽는 현재 방식이 상태와 비용을 더 명확하게 보여 준다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {


    public static void main(String[] args) throws Exception {
        countOfAlphabet();
    }

    public static void countOfAlphabet() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        int[] result = new int[26];
        for (char ch : str.toCharArray()) {
            result[ch - 'a']++;
        }

        for(int i : result) {
            out.write(i + " ");
        }
        out.flush();
        out.close();
        in.close();

    }
}