- Date : 2020.10.27(화)
- Time : 60분
- 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
for i in queries:
for j in words:
if len(j) == len(i):
if (i[0] == "?") and (i[i.rindex("?")+1:] == j[i.rindex("?")+1:]) :
answer[t] += 1
elif (i[0] != "?") and i[:i.index("?")] == j[:i.index("?")] :
answer[t] += 1
t += 1: for문과 인덱스 슬라이싱을 통해 구현해봤는데, 정답은 모두 맞았지만 효율성 테스트에서 3개나 시간초과가 떴다. 이를 위해 검색해보니 자동완성과 같은느낌의 문자열 찾는 trie를 이용해야한다고 한다. 하지만 나는 trie보다는 이분탐색이 더 익숙해서 이쪽으로 해보았다.
가사검색_틀린코드.py
- Trie 는 트리(Tree) 자료 구조의 일종. Trie 에서 어떤 문자열을 검색할 때의 시간 복잡도는 O(m) 밖에 안된다(m: 문자열의 최대 길이). 그래서 다른 자료 구조에 비해 문자열을 검색하는 데 특화된 자료 구조라고 한다.
for word in words:
cands[len(word)].append(word)
reverse_cands[len(word)].append(word[::-1]): 먼저 받아온 가사들을 defaultdict()에 정렬해준다. defaultdict는 dict의 서브 클래스로, 인자로 주어진 객체의 기본값을 딕셔너리의 초기값으로 지정할 수 있다. 여기에서는 길이를 초기값으로 지정해줬다. 그래서 가사 길이별로 분류를 해줬다. 그리고 반대로도 만들어준 이유는 "?"가 접두사 혹은 접미사로 들어가기 때문에 접두사로 들어갔을 경우를 위한 것이다.
for query in queries:
if query[0] == '?':
lst = reverse_cands[len(query)]
start, end = query[::-1].replace('?','a'), query[::-1].replace('?','z')
else:
lst = cands[len(query)]
start, end = query.replace('?','a'), query.replace('?','z')
answer.append(count_by_lange(lst, start, end)): 이제 "?"가 접두사에 있는지 접미사에 있는지에 따라 배열을 선택해 준 다음에 "?" 인 부분을 'a'와 'z'로 바꾼다. 그 이유는 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있기 때문이다. 그리고 이분 탐색을 통해 a-z사이의 글자에 있는지를 검색해주는 것이다. 효율성 문제는 너무 어렵다...