[BOJ] 10809번 - 알파벳 찾기

---

문제설명

https://www.acmicpc.net/problem/10809

10809번: 알파벳 찾기

사고과정

• 처음에 이진 탐색 라이브러리를 사용할까 했지만 a가 b앞에 나오는 경우도 인덱스 0으로 출력되기 때문에, 그리고 문자열 길이가 최대 100이고 알파벳은 총 26개니까 선형탐색을 해도 최악의 시간복잡도 $O(100 x 26)$이 나오기 때문에 이중 Loop로 선형 탐색을 진행했다. 단, 바로 첫번째 글자가 나오면 중첩 loop를 빠져나오도록 했고 선형탐색 하기 이전에 우선 해당 문자열이 있는지 없는지 찾기 위해 count 함수로 찾고 들어갔다. 만약에 해당 알파벳이 문자열에 없다면 continue로 중첩 loop로 가지 않고 바로 다음 loop를 진행하도록 설정했다! 
• 다행히 풀었다!

풀이

import sys

input = sys.stdin.readline
string = input().rstrip()
# 최악 시간 복잡도: 26 x 100(문자열 최대길이) = 2600번 연산
for i in range(0, 26):
    alpha = chr(i + ord('a'))
    if string.count(alpha) == 0:
        print(-1, end=' ')
        continue
    # 선형탐색
    for j in range(len(string)):
        if string[j] == alpha:
            print(j, end=' ')
            break