[프로그래머스/알고리즘] 자동완성

자동완성

코드 엉망이네 멋지게 푸는 방법을 모르겠습니다 ㅠㅠ;

입출력 예제

words : ["go","gone","guild"]

result : 7;

해결 방법

저는 이 문제를 풀기 위해서 트리구조를 이용했습니다.

문자만 있기 때문에 해당 문자의 이어지는 tree를 계속 이어서 만들었습니다.

words를 길이순으로 정렬해줍니다. ex) gone이 go보다 먼저 있을 경우 안됩니다.(적어도 제코드에서는)

그리고 데이터를 집어 넣는데

입출력 예제를 예시로 처음에 go를 먼저 할때 g라는 트리에 count를 1 증가 시킵니다.

그다음 g의 o위치의 트리를 만들어서 o 위치의 트리로 이동한 후 count를 1 증가시킵니다. 그리고 마지막이라는 것을 표시하기 위해서 o번째에 flag를 달아줍니다.

그 다음 gone에서 g를 할때 count가 1이 있을 경우 이미 방문되어있기 때문에 answer값을 1를 증가 시키고 count도 1증가 시키고 1보다 클 경우 answer를 1를 또 증가 시켜줍니다. 

이렇게 하면 go에서 g를 1번 눌러야 하는거고 gone에서 g도 역시 1번 눌러야하기 때문에 2가 증가되었습니다. (answer : 4)

그다음 o로 이동하면 count는 2가 되고 answer는 2가 증가해서 4가 될것입니다. 근대 o위치에서는 flag가 go에서 달아놨습니다. 여기서 answer 1개 빼줍니다. 이유는 마지막에 words의 갯수를 더해줘서 맞추려고 하기 때문입니다.(answer :3)

그다음 n으로 가면 count 1증가하고 e로 가면 count 1증가합니다. 그리고 flag를 e에 달아줍니다.

guild에서 g로 가면 count가 2에서 3으로 증가하고(answer 1증가) u, i, l,d 각각 count 1이 증가하고 d에서 flag를 달겠네요

그러면 총 answer는 4가 되고 여기에 words의 size만큼 더해줘서 7이 됩니다. 

처음에 queue방식으로 풀다가 시간초과나서 이렇게 풀었내요.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool Pred(string a, string b) {
	return a.length() < b.length();
}
struct Tree {
	int count;
	bool flag;
	Tree * next[26];
};

int solution(vector<string> words) {
	int answer = 0;
	int i;
	Tree tree[26] = { 0,false,NULL };
	sort(words.begin(), words.end(), Pred);
	for (i = 0; i < words.size(); i++) {
		Tree * iterator = &tree[words[i][0] - 'a'];
		for (int j = 0; j < words[i].size(); j++) {
			if (iterator->count == 1){
				answer++;              
            }
    		iterator->count++;
			if (iterator->count > 1) 
				answer++;
			if (iterator->flag == true){ 
				answer--;
                iterator->flag = false;  
            }
			if (j == words[i].size() - 1) {
                if(iterator->count==1)
				    iterator->flag = true;
				break;
			}
			if (iterator->next[words[i][j+1] - 'a'] == NULL) {
				iterator->next[words[i][j+1] - 'a'] = new Tree({ 0,false,NULL });
			}
			iterator = iterator->next[words[i][j+1] - 'a'];
		}

	}
	return answer+words.size();
}