문제 URL : programmers.co.kr/learn/courses/30/lessons/17685
코딩테스트 연습 - [3차] 자동완성
자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g �
programmers.co.kr
문제 접근법 : 자동완성 기능을 만들기위해 Trie구조를 사용하는것이 핵심입니다.
이것은 이론적인 말로만 설명을 듣기는 어려우니 그림으로 표현하겠습니다.
이런구조의 트라이구조형태를 만듭니다. 글씨가 좋지않아서 죄송해요 ㅠ.ㅠ
접근1:글자하나하나씩 카운트의 개수를 넣어주는 변수가 필요합니다.
접근2: 인제 해당 문자열을 찾습니다. world를 찾을때 l의 카운트 개수가 1입니다. 이게 1일때 지나온경로의 깊이를 구해 리턴해주면 됩니다.
접근3: 만약 war같이 중복되어있을땐 마지막 널문자열까지 왔다면 깊이는 한개더 탐색을 하게되서 깊이를 하나 빼주고 리턴해주면 됩니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
struct trie{
bool terminal = false;
int cnt = 0;
trie * next[26];
trie(){
memset(next, 0, sizeof(next));
}
~trie(){
for (int i = 0; i < 26; i++)
{
if (next[i])
delete next[i];
}
}
void insert(string &s, int idx = 0)
{
if (s[idx] == '\0')
{
terminal = true;//사실 터미널인지는 쓸필요가 없음
return;
}
int cur = s[idx] - 'a';
if (next[cur] == NULL)
next[cur] = new trie;
next[cur]->cnt++;//현재의 문자열 카운트개수를 증가시켜줌
next[cur]->insert(s, idx + 1);
}
void find(string &s, int &cnt, int idx = 0)
{
cnt++;
if (s[idx] == '\0'){//널문자까지 탐색했다면 깊이를 한개더 증가시켜서 탐색해준거니 -1해줘야함
cnt--;
return;
}
int cur = s[idx] - 'a';
if (next[cur]->cnt == 1){//카운트가 1인거는 바로 자동완성이 가능함
return;
}
next[cur]->find(s, cnt, idx + 1);
}
};
int solution(vector<string> words) {
int answer = 0;
trie tr;
for (int i = 0; i < words.size(); i++)
tr.insert(words[i]);
for (int i = 0; i < words.size(); i++)
{
int cnt = 0;
tr.find(words[i], cnt);
answer += cnt;
}
return answer;
}
|
cs |
모르는점 혹은, 궁금한점 혹은 논리적으로 맞지않느것이 있다면 언제든 댓글을 이용해주시길 바랍니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 야근지수 (0) | 2020.09.09 |
|---|---|
| 프로그래머스 섬 연결하기 (0) | 2020.09.09 |
| 프로그래머스 [1차] 뉴스클러스터링(2018 KAKAO BLINED RECRUITMENT) (0) | 2020.09.09 |
| 프로그래머스 순위 (0) | 2020.08.30 |
| 프로그래머스 지형 이동(Summer/Winter Coding(2019)) (0) | 2020.08.30 |
