cjwcjswo   2년 전

검색어와 검색빈도수가 주어졌을때 검색창에 사용자로부터 검색어를 입력받는 순간마다 검색어 힌트를 검색 빈도수순으로 출력하시오.

ex)

검색어 | 검색빈도수

apple | 50

apply | 25

appear | 42

bear | 5

beer | 90

cat | 62

car | 24

cmd | 52

acm | 66


이런 입력자료가 주어졌을때 사용자가 a를 타이핑하면 a로 시작하는 단어를 검색빈도수 순으로 출력하는것을 어떻게 알고리즘으로 구상할것인가? 라는 질문이였습니다.

단순히 저는 Map의 key값에 검색어, value값에 검색빈도수를 넣고 사용자가 단어를 타이핑할때마다 Map안에 key값의 요소드를 매칭해서 맞는 검색어들을 빈도수대로 정렬해서 출력한다라고 생각했는데 Map안의 key값들을 검사하는 시간 n과 따로 정렬을 해야되는 시간복잡도 nlogn이 사용자가 검색어를 타이핑하는 순간마다 이루어지려면 매우 비효율적이라는 답변을 들었습니다.

혹시 명쾌한 해답이 있나요?

3587jjh   2년 전

트라이를 이용하라는게 아닐까싶네요

fortescape   2년 전

저랑 같은 곳에서 같은 날에 보신분 같네요. 그날 진짜 고생 많으셨습니다..

저는 이거 트라이 + 해시테이블 + 우선순위큐를 사용한 해법을 제시했고, 가능은 할 것 같은데 좀 비효율적이라고 답변 받았었습니다. ㅠㅠ

(처음에 별 생각 없이 있는 지식 다 꺼내보겠다고 아호코라식까지 껴서 얘기했었는데, 백링크가 여기서 필요한 이유가 있을지 반문하셨고 저도 '아차!'싶어서 철회했죠..)

따로 찾아본 결과, '증분 검색 알고리즘'이나 '검색엔진 자동완성 알고리즘' 같은걸로 찾아보면 어느 정도 나오는 것들이 있는데 여전히 잘 모르겠어요.

B-트리 같은 것들을 사용해서 하면 될 것 같다는 막연한 느낌 정도는 있는데 생각난 김에 더 찾아봐야겠네요

yukariko   2년 전

실제 데이터베이스가 이런식의 쿼리를 지원하니 거기에 힌트가 있을것 같습니다.

제가 알기론

B+ tree를 포함한 몇가지 자료구조를 가지고 성능 예측을 통해 어느것이 더 효율적일지 여부를 빠르게 계산해서

그것을 수행하는 방식입니다.

h0ngjun7   2년 전

상당히 흥미로운 문제네요.

저라면 트라이 + 머지 소트 트리를 써서 풀 것 같습니다. 

댓글을 작성하려면 로그인해야 합니다.