https://programmers.co.kr/learn/courses/30/lessons/17685
코딩테스트 연습 - [3차] 자동완성 | 프로그래머스
자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하
programmers.co.kr
트라이 자료구조의 활용을 의도한 문제.
트라이 자료구조의 의미와 Python 구현 방법은 https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
파이썬에서 Trie (트라이) 구현하기
들어가며: "자동 완성" 기능에 대한 이야기 구글에서 어떤 단어를 검색창에 치면 그 단어로 시작하는 다른 키워드를 보여주는데요, 이런 걸 자동 완성(Autocomplete) 라고 합니다. 자동 완성을 구현 하려면 키워..
blog.ilkyu.kr
에서 확인할 수 있다. Trie의 구현 방법도 이 포스트를 참고했다.
풀이의 핵심은 '더 이상 단어의 분기점이 없는 지점'을 찾는 것.
문제의 예시대로 설명하자면
1. go를 트라이 자료구조에 입력한다. 먼저 g라는 노드가 생성되고, 해당 노드 뒤에 o라는 노드가 생성되어야 한다.
g라는 노드를 생성하면, 노드 안에 possible_word라는 변수가 0으로 초기화되어 있다. 값을 1 더해준다.
o라는 노드도 마찬가지로, 생성한 다음 possible_word라는 변수에 1 더해준다.
이 상태에서는 'g'라는 단어가 주어졌을 때 만들 수 있는 단어의 개수는 1개다. 'go' 라는 단어. 'o'라는 단어도 마찬가지다.
즉 g나 o라는 단어의 possible_word 변수 값은 1이다.
2. gone이 입력으로 들어온다.
먼저 g를 입력으로 받는다. g라는 노드가 이미 있으므로, possible_word 변수에 1을 더해준다.
다음 o 변수도 마찬가지로, possible_word 변수에 1을 더해준다.
이제 n이라는 변수가 들어온다. 단어 n을 가진 노드는 아직 없으니, n 노드를 생성한 다음 o 노드 뒤에 n 노드를 연결해 준다.
새로 생성한 노드이므로 possible_word 값은 0으로 초기화되어 있다. 이 값에도 1 더해주자.
이런 식으로 진행하면, 'g'라는 단어의 possible_word는 2, 'o'라는 단어의 possible_word도 2, 'n'의 possible_word는 1이 된다.
만약 gone을 찾아야 하면, g -> o -> n 순서대로 트라이를 순회하면서 possible_word 값이 1일 때까지 확인하면 된다.
1이면 그 밑으로는 더 볼 필요가 없게 된다.
go를 찾아야 할 경우, o까지 찾았는데 possible_word가 2이다. 이럴 때는 그냥 'go'라는 단어 길이를 더해주면 된다.
로직을 구현한 코드는 아래와 같다.
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 14889. 스타트와 링크 (0) | 2019.11.11 |
|---|---|
| [Python] 프로그래머스. 2020 카카오 recruit - 가사 검색 (Level 4) (1) | 2019.11.10 |
| [Python] 백준 14503. 로봇 청소기 (0) | 2019.11.08 |
| [Python] 프로그래머스. 기지국 설치 (Level 3) (0) | 2019.11.07 |
| [Python] 프로그래머스. 2019 카카오 recruit - 후보 키 (0) | 2019.11.06 |