알파벳 찾기 [ Python ] [ 백준 : 10809 ]

문제

 

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

 

입력

 

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

 

출력

 

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

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

 

---

풀이 및 회고

 

처음에 문제를 봤을때 잘 이해가 되지 않았다. 무슨말이지.. 싶었는데 한참보다보니 입력한 문자열에 순서를 저장하고 그 순서를 알파벳의 위치에 맞게 넣는 것이었다. 어떻게 할지 고민중에 딕셔너리를 활용할지 문자열 자체를 사용할지 고민하다 문자찾기를 할때 사용하는 메소드가 없나 찾아봤다. find() 메소드는 이 문제 풀이에 도움을 줄 수 있을거라 생각했고 적중하였다. 알파벳을 순서대로 적어놓은 문자열을 만든 뒤 find 를 활용해 인덱스가 어디인지 찾고 출력하는 방식이다. 또 마침 좋았던 특징은 그 인덱스가 없다면 -1 을 반환한다는 것 !

s = input()

alpha = 'abcdefghijklmnopqrstuvwxyz'

for i in alpha:
    print(s.find(i), end = ' ')

# find 는 해당 값을 찾으면 인덱스의 위치를 반환하고, 해당 인덱스가 없으면 -1을 반환한다.

이렇게 풀고나서 문제에 대해 피드백을 받았는데 이 문제는 시간 복잡도에 문제가 있었다. 문제는 정답이긴 하나 효율적이지 못한것.

겉보기엔 시간복잡도가 O(n) 같아 보이나 find 메서드 안에서 또 반복하기 때문에 시간복잡도가 증가한다. 즉 이 코드는 시간 복잡도가 O(n^2) 가 되는 것이다. 앞으로 알고리즘 문제를 더 풀려면 이러한 시간복잡도 는 정말 중요하기 때문에 고려하는 습관이 필요할 것 같다.

알차게 배웠습니다!