[자바]백준 10809번 알파벳 찾기[문자열][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

 

내가 문자열관련 문제만 보면 어려워서 그런 건지 무서워하는 경향이 있다.

그냥 문자열만보면 어떻게 접근해야 하는지도 모르겠고 어떻게 풀어야 좋은 시간복잡도를 줄일 수 있을까 생각이 들면서 무서워하는 경향이 있다. 그래서 이제는 문자열 문제를 브론즈 문제부터 쭈욱 풀어보려고 한다.

내 점수는 멈춰있겠지만... 6점만 더 맞으면 골드 3인데 한동안 골드 4일 것 같다.

 

 

문제

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

 

 

알고리즘 분류

• 구현
• 문자열

 

문제 설명

쉽게 설명해 단어가 주어지는데 단어에 사용된 알파벳의 위치를 알파벳 순서대로 출력하라는 말이다.

 

해설

해당 문제는 여러 가지 푸는 방법이 있다고 생각한다.

• 아스키코드를 이용하는 방법(추천, O(n))
• 자바 내장함수를 사용하는 방법(O(n^2))
• 이중 for문 사용해서 하는 방법(O(n^2))
• 등등

아스키코드는 간단하게 문자를 숫자로 표현하는 코드라 생각하면 되고, 아래 것들만 우선 기억하면 된다.

• A (65) ~ Z(90)
• a(97) ~ z(122)

그다음 아래 순서대로 풀면 된다.

1. 단어를 반복문으로 순서대로 알파벳을 확인
2. 알파벳(소문자)을 'a'로 빼주면 a(0) ~ z(25)와 같이 index로 사용하기 좋게 나온다. 
   
   • 만약 빼주는 게 기억 안 나면, 그냥 a(97) ~ z(122)로 사용하면 되다.
   • 단, 알파벳 위치를 담고 있는 배열의 공간을 123으로 확보해야 한다. 
   • 출력도 index 97부터 해줘야 한다.
   • 그냥 빼주는 게 최고
3. 해당 알파벳을 단어의 위치 값을 알파벳 위치를 담고 있는 배열에 저장

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String s = br.readLine();
        int[] alphaPositions = new int['z' - 'a' + 1];
        Arrays.fill(alphaPositions, -1);

        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            
            if (alphaPositions[index] == -1) {
                alphaPositions[index] = i;
            }
        }

        for (int alphaPosition : alphaPositions) {
            bw.write(alphaPosition + " ");
        }
        
        bw.write("\n");
        bw.flush();
        bw.close();
        br.close();
    }
}