[2020 KAKAO 코딩테스트 1차] 4번 - 와일드카드

2020 KAKAO BLIND RECRUITMENT 1차 코딩 테스트

[2020 카카오 코딩테스트] 문제 및 후기/예상 커트라인

4번 - [와일드카드]

문제 해설

효율성 테스트가 포함된 문제입니다. 마지막까지 효율성 테스트 2번을 통과하지 못했습니다..

검색 키워드 제한사항에서 "검색 키워드는 중복될 수도 있습니다"라고 적혀있었기 때문에 중복된 것을 반복해서 계산하지 않으면 통과할 수 있을 것이라고 생각했습니다. 따라서 각 키워드별로 한번 계산한 것은 dictionary에 저장해 두었습니다.

 

저는 위 그림처럼 두 개의 dictionary를 만들었습니다. 와일드카드가 접두사인 경우 q_dict_from_zero에 추가하였고, 접미사인 경우 q_dict에 추가하였습니다.

해시 함수를 잘 사용해야 할 것 같은데, 저는 실패했습니다..

 

 

 

파이썬(Python3) 코드

def solution(words, queries):
    '''
    :param words: 가사에 사용된 모든 단어들이 담긴 배열
    :param queries: 찾고자 하는 키워드가 담긴 배
    :return: 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 담은 배열
    '''
    # 접미사가 와일드카드인 경우 q_dict
    # 접두사가 와일드카드인 경우 q_dict_from_zero
    q_dict = {}; q_dict_from_zero = {}
    answer = []

    for q in queries:
        '''
        qlen: 키워드 q의 길이
        qnum: 와일드카드 문자의 개수
        qidx: 첫번째 와일드카드 문자의 index값
        '''
        qlen = len(q); qnum = q.count('?'); qidx = q.find('?')

        if qidx == 0:
            if q in q_dict_from_zero:
                answer.append(q_dict_from_zero[q])
            else:
                cnt = 0
                for w in words:
                    if len(w) == qlen:
                        if w[qnum:] == q[qnum:]:
                            cnt += 1
                q_dict_from_zero[q] = cnt
                answer.append(cnt)

        else:
            if q in q_dict:
                answer.append(q_dict[q])

            else:
                cnt = 0
                for w in words:
                    if len(w) == qlen:
                        if w[0:qidx] == q[0:qidx]:
                            cnt += 1
                q_dict[q] = cnt
                answer.append(cnt)

    return answer

 

[2020 KAKAO 코딩테스트 1차] 1번 - 문자열 압축