2020 KAKAO BLIND RECRUITMENT - 가사 검색

안녕하세요. 오늘의 문제 풀이는 LEETCODE가 아닌 KAKAO 문제를 들고 와봤습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/60060

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

 

당시 2020 KAKAO BLIND 채용 과정을 밟고 있었던 제가 풀었던 문제였는데요. (효율성은 통과 못 했.. ㅠ)

 

운이 좋게도 본 코딩 테스트를 통과하고, 2차 코딩 테스트까지 갔더랬죠.

 

그럼 뭐해 떨어졌는데

 

쉬벌

어쨋든 당시 못 풀었던 문제 복기나 해볼겸 건드려 봤습니다.

 

갑시다 !

---

본 문제는 가사를 담고 있는 리스트 words와 알고 싶은 단어를 포함한 queries가 동시에 존재합니다.

 

그래서 queries에 포함한 words가 몇 개냐? 를 물어보는 문제라 은근 간단해보이지만, 실상은 그렇지 않습니다.

 

범위가 words가 100,000개 queries가 100,000개 브루트 포스로는 100,000 * 100,000개로 효율성 테스트는 통과 못한다고 봐야죠.

 

그렇다면 저희는 좀 더 시간을 줄일 수 있는 자료구조 혹은 알고리즘을 사용해야합니다.

 

무엇이 있을까요?

 

그 때 당시엔 몰랐지만, 문제를 다시보니 저는 카카오가 정말 친절하다는 것을 느꼈습니다.

 

그걸 어디서 느꼈냐? queries에서 '?'가 시작과 끝에만 존재한다는 것입니다.

 

즉, 단어의 첫 부분 혹은 마지막 부분은 반드시 알 수 있다는 점인데, 이 점을 활용할 수 있는 자료구조가 무엇이 있을까요?

---

저희는 Trie(트라이)라는 자료구조를 사용해 볼겁니다.

 

https://en.wikipedia.org/wiki/Trie

Trie - Wikipedia

Trie(트라이)는 문자열을 담을 수 있는 자료구조로서, 자동완성 기능에서 자주 사용되는 자료구조입니다.

 

막 그런거 있잖아요. 검색창에 app까지만 검색했는데, apple, application 등 이렇게 뜨는거 처럼요. 이게 Trie(트라이) 자료구조를 이용한 기능이죠.

 

본 포스팅은 문제 풀이에 집중할 것이기에, Trie가 무엇인지 헷갈리시면 아래 글을 보시고 오시는 것을 추천드립니다.

https://ggodong.tistory.com/165

5670 - 휴대폰 자판 (Trie, 정적 풀이)

자 그럼 Trie가 뭔지 알겠고, 이를 어떻게 해결할 것이냐

 

우선 result의 조건을 먼저 살펴봅시다.

 

queries가 result에 카운팅 (+1)이 되려면, 2가지 조건을 만족해야합니다.

 

1. ??를 제외한 queries가 단어와 동일하다.

2. ??를 포함한 queries의 길이가 단어의 길이와 동일하다.

 

이 두 가지 조건을 만족해야 result에 카운팅이 되어야합니다.

 

1번 조건의 경우엔 Trie로 가능하겠다만, 길이는 어떻게 파악을 할까요? 물론 endpoint 조건을 잘 짜신다면, 길이도 파악이 가능하겠죠.

 

하지만, 저희는 보다 쉽게 생각하기 위해서 각 길이마다 Trie를 전부 만들 생각을 해보도록 합시다.

 

단어의 길이는 1 ~ 10,000까지이고, 이를 이용한 t_a = [Trie() for _ in range(10001)]를 만든다는 겁니다.

 

이렇게 하면 endpoint는 필요가 없겠죠. 길이를 알고 탐색을 하니 굳이 endpoint가 필요 없죠.

 

"fro??"라는 queries가 들어오면 t_a[len("fro??")] Trie에서 탐색을 하면 정답을 찾을 수 있어야 합니다.

 

자, 그렇다면 Trie를 구성할 메소드 insert, search를 구현하면 될 것이고, Trie를 구성할 Node class를 만들면 문제가 해결 되겠군요 !

 

Nope !!!

"????o"처럼 뒤에서 문자를 찾는 경우엔 어떻게 하실건가요 !

 

그렇기에 저흰 t_a와 같이 문자를 뒤집어서 저장할 r_a를 같이 만들겁니다. "frodo"라는 문자를 t_a에 저장하고, "odorf"를 r_a에 저장한다면, "????o"의 queries도 탐색이 가능하겠죠 !!

 

여기까지가 끝입니다.

 

당시 코테 볼 때 저를 힘들게 한 문제가 이렇게 쉽게 풀리니 좀 신기하네요.

 

코드 봅시다.

class Node:
    def __init__(self):
        self.alpha = {}
        self.count = 0

class Trie:
    def __init__(self):
        self.root = Node()
        
        
    def insert(self, word):
        temp = self.root
        
        for w in word:
            if temp.alpha.get(w):
                temp = temp.alpha[w]
            else:
                temp.alpha[w] = Node()
                temp = temp.alpha[w]
            temp.count += 1
    
    def search(self, que):
        cnt = 0
        if que == '':
            for val in self.root.alpha.values():
                cnt += val.count
            return cnt
        temp = self.root
        for w in que:
            if temp.alpha.get(w):
                temp = temp.alpha[w]
                cnt = temp.count
            else:
                return 0
        return cnt
    
    
def solution(words, queries):
    t_a = [Trie() for i in range(10001)]
    r_a = [Trie() for i in range(10001)]
    
    # words => Tries
    for word in words:
        t_a[len(word)].insert(word)
        r_a[len(word)].insert(word[::-1])
        
    # Search => queries
    answer = [0 for _ in range(len(queries))]
    for idx, que in enumerate(queries):
        if que[0] != '?': # queries => t_a
            s_que = que.split('?')[0]
            answer[idx] = t_a[len(que)].search(s_que)
        else: # queries => r_a
            s_que = que.split('?')[-1]
            answer[idx] = r_a[len(que)].search(s_que[::-1])
    
    return answer

위 설명과 또~~~옥같이 구현했습니다. 주석도 달려있어서 보시기 어렵지 않을겁니다 !

---

이상 2020 KAKAO BLIND RECRUITMENT - 가사 검색 였습니다. ^_^