백준 10809 Java - 알파벳 찾기

문제 이름 : 알파벳 찾기

---

문제

알파벳 소문자로만 이루어진 단어 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

---

나는 이 문제를 맞닥뜨렸을 때, 그냥 문자열 문제인가보다... 하고 넘겼었다.

물론, 문자의 첫 번째 출력 순서를 a ~ z 까지 답해야 하는 문제이므로,

큰 단위에서는 문자열 문제가 맞다.

조금 더 관심사항을 분리해 보면, 이 문제는 단순한 문자열 문제는 아니다.

초심자들이 char 즉, 각각의 문자에 대해 친숙해 지도록 만드는 문제이다.

String 객체와 char 타입의 변수의 상관관계와 변환을 익숙해 지게 만드는 것이 목적인 문제이다.

그리고 하나 더 있는데, a ~ z 까지의 첫 번째 출력 순서를 만들 배열을

어떤 방식으로 만들 것인가? 하고 묻는 문제이다.

나는 이러한 유형의 문제를 많이 풀었으므로, 바로 길이는 z - a + 1

이렇게 선언 할 것이다.

그런데 왜 + 1 이 붙었는지에 집중해야 한다.

만약 '1' 문자열부터, ... '14' 문자열을 담는 배열을 만든다면,

이 배열의 크기는 얼마인가?

당연히 크기는 14 일 것이다.

그렇다면, str[14] 과 같이 선언된다.

그리고, 내부의 인덱스는 0 ~ 13 까지이다.

그렇다면, 'x' 라는 숫자 문자열부터 'y' 라는 연속된 숫자 문자열을 담는 배열을 만든다면,

이 배열의 크기는 어떻게 할당할 것인가? 식은 어떻게 만들어야 할까?

'2' 부터 '15' 라면, 위의 배열의 크기와는 상관없기 때문에, 똑같이 str[14] 이다.

'3' 부터 '16', '4' 부터 '17' 도 동일하다.

보다시피, 이제 크기를 정의할 수 있는 점화식은 나타났다.

연속된 수가 존재 할 때, 처음을 x, 마지막을 y 라고 말할 때,

이러한 연속된 수를 정확히 담을 변수의 크기 선언은

y - x + 1 이다.

• 2, 15 = 15 - 2 + 1 = 14
• 1, 14 = 14 - 1 + 1 = 14
• 5, 18 = 18 - 5 + 1 = 14

a 부터 z 의 순서를 담을 정확한 길이의 배열을 만들기 위해 빌드업을 했는데,

지금부터 시작 해 보자.

먼저, 출력물이 될 배열을 선언해야 하는데, a 부터 z 까지의 순서를 담아야 한다.

그렇다면, a 가 시작이며, z 가 마지막이다.

그런데 공교롭게도, 문자는 즉, ASCII 숫자이다.

그리고 a 부터, z 까지 ASCII 숫자로서 연속된 숫자로 나타내져 있다.

그리고 char 유형의 변수는 쉽게 (int) 로 변환이 가능하다.

위의 특성을 이용하여, 쉽게 코드를 제작 할 수 있다.

1. a 부터 z 까지의 순서를 담을 배열 생성

위에서 만든 y - x + 1 점화식을 사용한다면,

int[] arr = new int[(int)'z' - (int)'a' + 1] 이다.

이를 이용한다면, 굳이 a 부터 z 까지의 배열의 길이 몇인지 알 필요도 없다.

확실 한 것은, 정확히 a 부터, z 문자열에 알맞는 순서와 길이의 배열이 생성되었다는 것이다.

그렇다면, 문자열 의 문자를 추출했을 때,

위에서 생성한 배열에 어떻게 정확히 접근할까?

문자에 합당한 배열 접근

결국 문자열 에 속하는 문자 도 ASCII 로 치환된다.

만약에, 문자에 알맞는 배열 인덱스에 접근하고자 한다면,

arr[(int)(이번 문자) - (int)('a')] 로 접근하면 된다.

문자 a 를 ASCII 숫자화 시킨다면, 어떠한 문자가 들어오던,

그에 알맞는 순서의 인덱스로 접근 할 수 있다.

Example : arr[(int)('a') - (int)('a')] == arr[0]

배열의 인덱스 0 번은 a 이므로, 알맞게 접근이 가능하다.

자, 이제 문제를 풀기 위한 모든 준비가 끝났다.

이제 문제를 풀기 위한 순서를 만들어 보자 :

1. a 부터 z 까지의 순서를 담을 숫자 배열 생성
2. 배열의 모든 요소에 -1 로 초기화
3. 문자열 읽기
4. 문자열의 길이만큼 순회하며, 각 문자를 추출
5. 추출한 문자의 배열 인덱스에 접근
   • 만약 -1 이라면, 현재 반복중인 실제 인덱스 삽입
   • 만약 다른 숫자가 있다면, 넘어가 버리자
6. 문자열 길이만큼의 반복이 끝난 후, 모든 배열의 첫 번째 순서 출력

이제 이것을 코드로 풀어보자 :

Answer

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       // 문자들의 첫 번째 수를 담을 배열 생성 
       int[] arr = new int['z' - 'a' + 1];

       // 반복문 말고도 이러한 방식을 사용 할 수 있다.
       // 단순 배열에 대한 편의성 객체를 이용하여 내부의 값을 채움.
       Arrays.fill(arr, -1);

       String str = br.readLine();

       for(int i = 0; i < str.length(); i++) {
          char ch = str.charAt(i);

          /**
           만약 현재 문자 순서가 삽입되었다면, 값을 변경하지 않으며,
           현재 문자의 순서가 -1 로 삽입 된 적이 없다면, 현재의 인덱스로 변경한다.
           */
          arr[ch - 'a'] = arr[ch - 'a'] == -1 ? i : arr[ch - 'a'];
       }

       // System.out.print() 사용해도 되지만, StringBuilder 로 더 깔끔하게 만들 수 있다.
       StringBuilder sb = new StringBuilder();
       for(int i = 0; i < arr.length; i++)
          sb.append(arr[i]).append(" ");

       System.out.println(sb.toString());
    }
}