[프로그래머스] 가사 검색

출처: 2020 KAKAO Blind Recruitment

문제 링크: programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

문제에 대한 자세한 내용은 링크를 통해 직접 확인하시기 바랍니다.

 

이분 탐색 문제를 풀던 중 나온, 카카오 기출문제들이 으레 그렇듯 꽤 난이도 있는 문제입니다.

정확히는 정석대로 이분 탐색을 구현하는 것이 아닌, lower_bound와 upper_bound 함수를 이용하여 구현하는 방식입니다.

 

문제를 접근한 순서는 다음과 같습니다.

1. 각 단어를 길이에 따라 나눈다.
2. 각 단어 길이 배열을 알파벳 순서로 정렬한다.
3. 이진 탐색을 통해 쿼리의 단어로 시작하는 마지막 단어와 첫 단어의 인덱스를 구하고, 그 차이를 구합니다. (?를 a와 z로 대체한 후, 그 사이 구간의 갯수를 구하면 편합니다.)
4. 접두사가 ?로 시작하는 쿼리의 경우, 계산을 위해 reverse를 이용하여 문자열을 뒤집은 후 2~3의 과정을 수행한다.
5. 각 결과를 정답 배열에 저장한다.

별도로 두 개의 함수를 작성하였습니다.

countByRange 함수는 주어진 정렬된 문자열 배열 내에서, 시작점과 끝점 사이의 갯수를 구하는 함수입니다.

lower_bound와 upper_bound 함수를 사용했고, 예를 들어 찾고자 하는 단어가 'fro??' 라면, froaa ~ frozz 사이의 단어의 수를 구합니다.

replaceAll 함수는 문자열 내의 특정 문자를 다른 문자로 바꿔주는 함수입니다. ?를 a 또는 z로 바꾸는 역할을 합니다.