문제 : 가사 검색
풀이
해결에 필요한 핵심 아이디어: bisect 모듈 활용
해결 시나리오
•
주어진 가사 단어를 길이별로 묶어서 2차원 리스트에 새롭게 저장
◦
이진 탐색을 위해 해당 길이 별로 묶인 리스트를 오름차순 정렬
•
bisect 모듈을 활용하여 각각의 query 키워드와 일치하는 단어의 갯수 구하기
◦
query 키워드로 만들 수 있는 단어 중에서 가장 앞에 위치하는 경우
→ ?를 모두 a로 변환 ex) fro?? → froaa
◦
query 키워드로 만들 수 있는 단어 중에서 가장 뒤에 위치하는 경우
→ ?를 모두 z로 변환 ex_ fro?? → frozz
◦
각각의 단어가 들어갈 수 있는 인덱스를 구하고 서로의 차를 구하면,
해당 키워드와 일치하는 모든 단어의 갯수를 얻을 수 있음
•
‘?’ 가 키워드 앞에 붙는 경우는?
→ 위의 방식으로는 처리 불가하므로 같은 조건으로 만들어주자!
◦
가사 단어와 query 키워드를 모두 뒤집은 다음, 똑같이 탐색 진행
▪
슬라이싱 활용
word = 'hello'
word[::-1] # olleh
Python
풀이