일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 삼성 SW 기출문제
- 2019 KAKAO BLIND RECRUITMENT
- gcp
- 젠킨스
- 2019 카카오 개발자 겨울 인턴십 코딩테스트
- 프로그래머스
- map
- 카카오
- 2018 카카오 공채
- 2018 KAKAO BLIND RECRUITMENT 1차
- set
- 2020 카카오 공채
- 카카오 공채
- gradle
- 2018 카카오
- bfs
- 비트마스크
- 알고리즘
- CS 스터디
- c++
- 2018 KAKAO BLIND RECRUITMENT
- dfs
- Java
- 2020 KAKAO BLIND RECRUITMENT
- 2019 카카오 공채
- 삼성 SW 역량테스트
- 자바
- Baekjoon
- 백준
- 부스트코스
Archives
- Today
- Total
아무코딩
[2018 KAKAO BLIND RECRUITMENT 3차] 자동완성 본문
문제풀이
트라이 연습으로 매우 좋은 문제였다. 마지막에 카운트를 셀때는 조금 방법이 헷갈려서 시간이 걸린것 같다. 아직 트라이가 익숙하지 않아 전에 짰던 코드를 계속 참고하며 짜는데 연습이 좀더 필요한것 같다.
카운트를 셀때 count가 1인 경에는 더 내려가서 셀 필요가 없다 그때는 무조건 1개의 경우만 나오므로
소스코드
더보기
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
63
64
65
66
67
68
69
70
71
72
|
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer=0;
class Trie{
private:
int count;//자식 개수
bool finish;
Trie* next[26];
public:
Trie() : finish(false){
count =0;
for(int i=0;i<26;i++){
next[i]=NULL;
}
}
~Trie(){
for(int i=0;i<26;i++){
if(next[i])
delete next[i];
}
}
void insert(const char* key){
if((*key)=='\0'){//문자 끝일때
if(count==1){
finish=true;
}
return;
}
int cur = (*key)-'a';
if(!next[cur]){//다음이 NULL
next[cur] = new Trie();
}
next[cur]->count +=1;
next[cur]->finish =false;
next[cur]->insert(key+1); //그다음 글자 insert
}
void countNum(){
if(count>0){
answer += count;
if(count==1)
return;
}
if(finish){//finish면 끝
return;
}
for(int i=0;i<26;i++){
if(next[i])
next[i]->countNum();
}
}
};
int solution(vector<string> words) {
Trie* trie = new Trie();
for(int i=0;i<words.size();i++){
trie->insert(words[i].c_str());
}
trie->countNum();
return answer;
}
int main(void) {
cout<<solution({ "go","gone","guild" })<<endl;
}
|
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17685
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠 (0) | 2020.04.26 |
---|---|
[2018 KAKAO BLIND RECRUITMENT 3차] 압축 (0) | 2020.04.24 |
[프로그래머스 SQL] 보호소에서 중성화한 동물 (0) | 2020.04.18 |
[프로그래머스 49191] 순위 (0) | 2020.04.17 |
[2020 KAKAO BLIND RECRUITMENT] 길찾기 게임 (0) | 2020.04.13 |
Comments