Q30 가사 검색 (2020 카카오 신입 공채 기출)

코딩테스트 연습 - 가사 검색 | 프로그래머스 (programmers.co.kr)

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

 

책에 제한 시간이 1시간 30분이라고 나와있다. 난이도도 최상이라고 되어있다. 꽤나 어려운 문제인가보다.

 

아직 정답을 보지 않은 상태로 20분간 풀이 방법을 고민해봤다. 내가 생각하는 풀이 방법은 이렇다.

문제 예시 입력인 ["frodo", "front", "frost", "frozen", "frame", "kakao"]를 기준으로 보자.

먼저 이 words 리스트를 알파벳순으로 정렬한다.

frame frodo front frost frozen kakao

이런식으로 되겠지?

'fro??' 쿼리를 예로 들면, 이진 탐색으로 앞부분이 fro인 문자열들을 추려낸다. (fro로 시작하는 첫 번째 단어의 인덱스와 마지막 단어의 인덱스를 찾으면 될것같다)

frodo front frost frozen

그리고 fro??의 길이가 5이므로 위에서 길이가 5인 문자열의 개수를 센다.

frodo front frost로 총 3개.

 

흠.. 근데 이 문제는 효율성도 많이 중시하는 문제라 이렇게 풀면 안될거같다. 쿼리가 ????? 이런식으로 와버리면 모든 문자열에서 길이가 5인 문자열의 개수를 세야되니까 좀 비효율적이랄까..

 

정답에서는 어떻게 풀었는지 보자.

 

오.. 정답에서도 나와 유사한 방법으로 풀었다. 다른 점은, 처음에 문자열을 길이별로 나눠놨다는 거다. 나도 이 방법을 생각해보긴했는데, 길이별로 나누려면 2차원 리스트를 선언해야되고 좀 공간상으로 비효율적일거같아서 머릿속으로 reject했는데 이렇게 푸는 거였다니..

책의 정답페이지에서 제시하는 방법

1. 단어 리스트를 길이별로 나눈다.

2. fro??라는 쿼리가 들어왔다면 fro로 시작하는 첫 단어의 위치와 마지막 단어의 위치를 구하고 그 차이를 계산한다.

3. 와일드카드가 접두사로 등장하는 경우를 대비해 단어를 뒤집은 리스트도 만든다. ex)kakao -> oakak

약간 공간적인 효율성은 버리고 시간효율성에 몰빵한 느낌이다 ㅋㅋ 근데 요즘에 메모리야 워낙 크니까.. 문제 조건에서도 단어 개수가 1000만 단위가 아니라서 메모리 효율성은 좀 버려도 상관없을거같긴하다.

 

일단 코드 답안을 보지 말고 내 방식대로 짜보자.

...

짜보려고 했는데 이진탐색하는 부분에서 막혀버렸다..ㅎㅎㅋㅋㅋ;;;

책의 정답을 보니 bisect 라이브러리의 bisect_left와 bisect_right를 사용했다. fro??가 쿼리일때 froaa와 frozz로 검색을 하는 것이다. 일단 라이브러리 써서 구현하긴 했는데, 라이브러리가 없다면 이진탐색을 어떻게 할지 고민을 좀 더 해봐야될거같다. 

from bisect import bisect_left, bisect_right

def count(array, query):
    array = array[len(query)]
    
    if not array:
        return 0
    
    left = bisect_left(array, query.replace('?','a'))
    right = bisect_right(array, query.replace('?','z'))

    return right-left
    
def solution(words, queries):
    array = [[] for _ in range(10001)]
    array_r = [[] for _ in range(10001)]
    
    for word in words:
        l = len(word)
        array[l].append(word)
        array_r[l].append(word[::-1])
        
    for i in range(1,10001):
        array[i].sort()
        array_r[i].sort()
        
    answer = []
    for query in queries:
        if query[0] != '?':
            answer.append(count(array,query))
        else:
            answer.append(count(array_r,query[::-1]))
            
    return answer
    

 

완성된 코드는 진짜 짧고 간결하다 ㄷㄷ

참고로 이 문제는 정확도와 효율성을 따로 채점하는 문제인데, 위 코드로 채점하면 둘다 통과된다.

이걸 둘다 통과한 사람들의 비율은 그리 높지 않았다고 한다.

나는 정답지 안봤으면 손도 못댔을듯..ㅎ 오늘도 자괴감 1적립!

남는 시간에 이진탐색 복습이나 해야겠다..