[BaekJoon-10809] 알파벳 찾기

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

입력

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

출력

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, … z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.

만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

예제 입력 1

baekjoon

예제 출력 1

1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

첫 위치를 기록하는 방법

각 알파벳을 대상으로 문자열 전체를 26번 검색할 수도 있다. 하지만 문자 한 번 순회하면서 “아직 위치가 기록되지 않은 알파벳인가”만 확인하면 충분하다. 결과 배열을 전부 -1로 초기화한다. -1은 등장하지 않았다는 표시이자 아직 첫 위치를 쓰지 않았다는 표시다.

ch - 'a'는 소문자 a부터 z까지를 배열 0번부터 25번에 대응시킨다. 예를 들어 b는 1번 칸, o는 14번 칸이다. 문제의 입력이 소문자로만 제한되므로 인덱스 범위가 보장된다. 길이 26인 배열을 쓰는 이유는 입력 길이가 26이라서가 아니라 가능한 문자 종류가 26개이기 때문이다.

baekjoon에서 a를 읽는 인덱스는 1이므로 result[0]=1이다. o는 인덱스 5에서 처음 등장하고 6에서 다시 나타난다. 두 번째 o에서는 칸이 이미 5라서 덮어쓰지 않는다. 덮어쓰면 첫 위치가 아니라 마지막 위치를 출력하는 버그가 된다. 문제는 첫 글자의 위치를 0으로 세므로 루프의 i를 그대로 저장한다.

현재 인덱스	문자	변경 전 해당 칸	변경 후 해당 칸
0	`b`	-1	0
1	`a`	-1	1
5	`o`	-1	5
6	`o`	5	5

반복문의 불변식은 “처리한 앞부분에서 처음 나타난 위치가 기록되어 있고, 아직 나타나지 않은 문자는 -1이다”이다. 처음에는 모든 칸이 -1이므로 성립한다. 한 글자를 읽을 때 미기록 칸만 현재 위치로 바꾸면 최초 위치가 보존되고, 끝까지 읽으면 원하는 답이 된다.

길이를 L이라 할 때 시간은 초기화·출력 26칸과 문자열 순회로 O(L+26), 공간은 O(26)이다. z가 없는 단어에서는 마지막 칸이 -1이어야 하고, aaa에서는 a의 첫 위치 0을 유지해야 한다.

소스코드

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

public class Main {

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

    public static void alphabetFound() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        char[] chars = str.toCharArray();
        int[] result = new int[26];
        Arrays.fill(result, -1);

        for (int i = 0; i < chars.length; i++) {
            int idx = chars[i] - 'a';
            if (result[idx] == -1)
                result[idx] = i;
        }

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

    }
}