[프로그래머스] 3차_자동완성(C++)

[프로그래머스] 3차_자동완성(C++)

프로그래머스 자동완성

위 문제는 2018 카카오 블라인드 테스트에 나왔던 문제이다.

1. 문제

문제링크

2. 접근법

문제 접근 기본적으로 트라이 자료구조를 사용하는 문제이다. 트라이 자료구조는 접두사를 검색하거나 단어자체를 검색하는데에 특화된 문자열 집합 자료구조다. 문자 하나하나씩 카운트의 개수를 넣어주는 변수와 단어의 끝자리인지 판단하는 bool 자료형이 필요하다. 문자열을 찾을때 깊이가 1인 경우(이미 검색된 적이 있는 경우), 깊이가 1보다 큰 경우(그 뒤의 글자가 있는 경우) answer를 1증가 시킨다. 마지막 글자인 경우 하나 더 탐색을 하게 되므로 answer를 1줄인다. 단어의 끝자리인 경우 끝자리인지 판단하는 변수를 true로 바꾼다. 다음 글자 정보가 없다면 다음 글자를 초기화하고 포인터를 바꿔준다.

3. 코드

#include #include #include #include using namespace std; //오름차순으로 정렬 bool cmp_word(string a, string b) { return a.length() < b.length(); } struct Word { bool end; int depth; Word* next_word[26]; }; int solution(vector words) { int answer = 0; //26개 알파벳 초기화 Word dic[26] = { {false,0,NULL}, }; //오름차순으로 정렬 sort(words.begin(), words.end(), cmp_word); for (int i = 0; i < words.size(); ++i) { //루트노드 생성, 단어의 첫 알파벳 Word* next = &dic;[words[i][0] - 'a']; for (int j = 0; j < words[i].size(); ++j) { //검색된 적이 있다면 answer+1 if (next->depth == 1) ++answer; next->depth++; //검색된 적이 2번이상이면 answer+1 if (next->depth > 1) answer++; //마지막글자라면 그 전 글자를 쳤을때 자동완성되므로 1빼주고 false로 바꿈 if (next->end == true) { answer--; next->end = false; } //단어의 끝글자라면 end를 true로 바꿔주고 break if (j == words[i].size() - 1) { if (next->depth == 1) next->end = true; break; } //다음 글자에 대한 정보 생성 if (next->next_word[words[i][j + 1] - 'a'] == NULL) next->next_word[words[i][j + 1] - 'a'] = new Word({ 0,false,NULL }); next = next->next_word[words[i][j + 1] - 'a']; } } return answer + words.size(); }

4. 시간복잡도

이중for문으로 (입력된 단어의 수)*(해당 단어의 길이) 만큼 돌린다. 문제에서 주어진 입력된 단어의 수(N)과 입력된 단어의 총 길이의 합(L)이 아래와 같다.

2 <= N <= 100,000

N <= 100,000 2 <= L <= 1,000,000

따라서 결국은 많아 봐야 총 길이의 합만큼 돌리게 되므로 100만, 즉 1초내로 구현하기 충분하다.

5. 결과

from http://pro-grammers.tistory.com/26 by ccl(A) rewrite - 2021-08-23 23:00:10