가사 검색 (60060번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 가사 검색 (60060번)

난이도 : Lv 4

Time Complexity : O( 문자열 전체 길이 )

알고리즘&자료구조 : Trie (트라이)

 

---

2020 KAKAO BLIND RECRUITMENT 기출문제이다.

 

Trie를 적용해서 풀었는데,

queries로 Trie를 만들고 words로 확인하니까 효율성 테케 1, 3번을 통과하지 못했다.

결국 words로 Trie를 만들고, queries로 확인하니까 통과할 수 있었다.

(Trie를 각 단어의 길이 별로 각각 만들어준 것도 영향이 있었다.)

 

< 전체 코드 >

def put(word, trie):
    for char in word:
        trie['cnt'] = trie.get('cnt', 0) + 1
        trie[char] = trie.get(char, {})
        trie = trie[char]


def count(word, trie):
    for char in word:
        if char == '?':
            return trie.get('cnt', 0)
        trie = trie.get(char, False)
        if not trie:
            return 0


def solution(words, queries):
    front, back = [{} for _ in range(10001)], [{} for _ in range(10001)]
    for word in words:
        l = len(word)
        put(word[::-1], back[l])
        put(word, front[l])
    for i, word in enumerate(queries):
        l = len(word)
        queries[i] = count(word[::-1], back[l]) if word[0] == '?' else count(word, front[l])
    return queries

---

 

① queries와 words의 각 단어의 최대 길이는 10000 이하이므로,

길이가 10001인 리스트 2개 (front, back) 를 만들어준다.

 

리스트의 각 원소는,

해당 원소의 index 만큼의 길이를 갖는 단어들로 만들어지는 Trie가 된다.

[ ex) front[5] → 길이가 5인 단어들의 Trie ]

 

front는 "ab???"와 같이 "?"가 뒤에 있는 단어들을 확인하는 Trie들의 리스트이다.

back은 "???ba"와 같이 "?"가 앞에 있는 단어들을 확인하는 Trie들의 리스트이다.

 

front, back = [{} for _ in range(10001)], [{} for _ in range(10001)]

 

 

 

② words에서 word를 하나씩 꺼낸 후,

해당 word의 길이에 맞는 Trie를 찾아서 업데이트한다.

기존 word로 front를 업데이트하고, word를 거꾸로 뒤집어서 back을 업데이트한다.

 

def put(word, trie):
    for char in word:
        trie['cnt'] = trie.get('cnt', 0) + 1
        trie[char] = trie.get(char, {})
        trie = trie[char]
        

for word in words:
    l = len(word)
    put(word[::-1], back[l])
    put(word, front[l])

 

 

 

③ queries에서 word를 하나씩 꺼낸 후,

첫 번째 문자가 "?"라면 back[ len(word) ] 에서 갯수를 세고,

아니라면 front[ len(word) ] 에서 갯수를 세서 반환한다.

 

def count(word, trie):
    for char in word:
        if char == '?':
            return trie.get('cnt', 0)
        trie = trie.get(char, False)
        if not trie:
            return 0
            

for i, word in enumerate(queries):
    l = len(word)
    queries[i] = count(word[::-1], back[l]) if word[0] == '?' else count(word, front[l])
return queries