log 2021-09-03
sport
코테연습 - kakao 2020
가사 검색
쿼리로 매칭되는 단어 개수 구하기. 쿼리 개수 ~ 10만, 단어 개수 ~ 10만이지만 쿼리 문자 길이 ~1만, 단어 문자 길이 ~1만 쿼리 문자 길이 합 ~ 100만, 단어 문자 길이 합 ~ 100만이므로 단순 반복으론 안 될 것이다.
생각해보자. 중첩된 것을 찾아서, 중첩의 계산을 최대한 줄이는 방향으로 한다면 좋을 것이다. 예를 들어, frod?와 fro??는, fro??가 frod?를 포함한다. 이를 활용할 수 없나? frod? < fro?? < fr??? < f???? < ????? froe? …
?가 시작이나 끝에만 있을 수 있는것도 어떤 힌트같은데..
접미사와 접두사 트리를 만들어서 카운팅을 해 놓으면, 쿼리에 대해서는 그 노드에 기록된 값만 읽으면 될 듯하다.
필요한 액션:
- 입력
- 단어를 읽어서, 글자 단위로 다음 작업 필요
- 앞 글자부터 문자로 인덱싱, 해당하는 노드에 카운트 추가
- ex: asd -> ‘’ +1, ‘a’ +1, ‘as’ +1, ‘asd’ +1
- 근데 이런 식으로 하면 너무 연산도 메모리도 많이 쓸 듯한데.
- 구현 결과 결국 이런 단순 방법으로는 시간초과가 나서 해결이 되지 않는다.
- 그러면 어떻게 해야 효율적으로 만드나??
결국 해설 봄. 트라이를 사용한다는 데, 뒤가 아니라 앞에 ?가 오는 경우에도 적용이 되는지 확인이 필요하다.
트라이를 구현해본 적이 없어서 일단 답 참고해서 구현해봐야 할 듯하다.
사실 원리 자체는 한 번 그림만 보면 대충 이해가 간다. 그런데 왜 이걸 만들 생각을 못했을까? 사실 효율적일 수 있다는 예상은 했는데, 트라이를 만드는 비용이 얼마나 드는지, 구현을 어떻게 하는지를 몰라서였다.
py solution
여기서 트라이 구현의 구조를 잘 익혀둘 필요가 있다. 또한, 이 문제에서 왜 트라이가 필요한지, 그리고 뒤쪽 ?를 매칭시키기 위해 반대 방향 접미사 트라이를 사용한 이유도 설명가능해야 한다.
또 눈여겨 볼 점은, 트라이를 만들 때 하위의 노드에 특수문자를 키로 길이를 배열로 만든다.
일단 트라이를 만들 때 각 아이템을 순회하면서, 그 반복문 내에서 새 포인터로 쓸 변수를 만들고, 그것을 루트부터 시작시킨다. 그래서 해당 아이템의 각 값에 대해 반복하면서 다음 작업을 한다:
- 키가 현재 노드에 없음 경우
- 새 노드 생성
- 현재 노드를 그 노드로 변경
- (필요한 경우) 깊이 정보에 추가
- 키가 현재 노드에 있을 경우
- 현재 노드를 그 노드로 변경
- (필요한 경우) 깊이 정보에 추가
이렇게 반복문 내에서 새 변수로 항상 루트부터 시작하기 때문에
그리고 반복문이 끝나면 터미널 노드임을 새 키를 지정하여 설정한다.
# calculate matching count of each queries for all words
def solve(words, queries):
# match for ???...?
all = 0
prefix = make_trie(words)
suffix = make_trie([word[::-1] for word in words])
# print('prefix', prefix)
# print('suffix', suffix)
# print('q, is_prefix, is_suffix, is_all')
ans = []
# print(prefix)
for q in queries:
# lookup prefix
is_prefix = q[-1] == '?'
is_suffix = q[0] == '?'
is_all = is_prefix and is_suffix
# print(q, is_prefix, is_suffix, is_all)
# cnt '?'s
qu = q.replace('?', '')
if(is_all):
ans.append(suffix['cnt'].count(len(q)))
elif(is_prefix):
# print('qu', qu)
res = lookup(prefix, qu)
# print('res', res, 'len', len(res))
# check depth(node)=depth
if '!' in res :
ans.append(res['!'].count(len(q)))
else:
ans.append(0)
elif(is_suffix):
res = lookup(suffix, qu[::-1])
# print('res', res, 'len', len(res), 'qu', qu, 'OO', suffix['o'])
if '!' in res :
ans.append(res['!'].count(len(q)))
else:
ans.append(0)
# print(ans)
return ans
solution = solve
def make_trie(words):
trie = {}
cnt = []
for word in words:
l = len(word)
cnt.append(l)
node = trie
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['!'] = [l]
else:
node = node[c]
node['!'].append(l)
node['#'] = True
trie['cnt'] = cnt
return trie
def lookup(trie, word):
node = trie
for c in word:
if c not in node:
return {}
node = node[c]
return node
Comments