구현 - 백준 10809

BOJ/백준 10809 - 알파벳 찾기

백준 10809 - 알파벳 찾기

1. 문제 분석

문제 이해

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

입력

• 첫째 줄에는 단어 S 입력
• 단어의 길이는 100은 넘지 않고, 알파벳 소문자로만 이루어져 있음

출력

• 각각의 알파벳에 대해서 a가 처음 등장하는 위치 ~ z가 처음 등장하는 위치를 공백으로 출력
• 어떤 알파벳이 단어에 포함되어 있지 않다면 -1 출력
• 단어의 첫 번째 글자는 0번째 위치

문제 핵심

• 26개의 소문자 알파벳 (a~z)으로만 이루어져 있다
• 초깃값 -1 을 숫자가 아닌 해당 알파벳이 아직 한 번도 안나왔다 라는 상태정보 활용
• 조건문을 가지고 최초 기록 보장해주는 것

---

2. 시간 복잡도

• 첫 번째 반복문은 배열 초기화 항상 26번만 실행되므로 상수 시간 복잡도 -> O(1)
• 두 번째 반복문은 문자열 순회 S의 문자열 길이만큼 순회하기 때문에 -> O(N)
• 세 번째 반복문은 배열 출력 arr의 배열길이 만큼 26번 돌기 때문에 -> O(1)

전체 시간 복잡도는 모두 더한 값이지만

💡 빅오 표기법에서는 가장 큰 영향을 미치는 최고차항만 남기고 상수와 계수는 무시
따라서 O(N)

---

3. 코드 구현

import java.io.*;

public class No_10809 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String S = br.readLine();
		int[] arr = new int[26];
		
		// 1. 배열의 모든 값 -1로 초기화
		for(int i = 0; i < arr.length; i++) {
			arr[i] = -1;
		}
		
		// 2. 문자열 길이 만큼 반복
		for(int i = 0; i < S.length(); i++) {
			char ch = S.charAt(i);
			if (arr[ch - 'a'] == -1) {
				
				// 같은 알파벳이 반복 등장하여도 조건문이 false가 되므로, 값은 갱신 불가
				arr[ch - 'a'] = i;
			}
		}
		
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}