[Programmers] 가사 검색

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

 

이분 탐색 알고리즘과 문자열 처리를 접목시킨 문제였습니다.

 

알고리즘은 다음과 같습니다.

• 주어진 단어들 전처리 진행
  • 단어의 길이에 따라 wordsByLength 배열에 단어들을 저장
  • 접두사에 와일드카드가 등장하는 쿼리를 효율적으로 처리하기 위해, 각 단어를 뒤집어서 reversedWordsByLength 배열에도 저장

 

• 쿼리 처리
  • 쿼리의 길이에 해당하는 단어 그룹이 없으면 0을 결과에 추가.
  • 쿼리의 첫 글자가 알파벳이면 와일드카드가 접미사에 있는 것이므로, '?'를 'a'와 'z'로 치환한 두 문자열 사이에 존재하는 단어의 수를 이진 탐색으로 구하고 ( leftQuery와 rightQuery는 주어진 쿼리 문자열에 포함된 와일드카드 문자 '?'를 각각 최솟값과 최댓값으로 치환)
  • 만약 쿼리의 첫 글자가 '?'이면, 쿼리를 뒤집은 후 동일한 방식으로 처리

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~