# 【Algorithm】 [프머] 2018 KAKAO BLIND RECRUITMENT 자동완성

(Algo) [프머] 2018 KAKAO BLIND RECRUITMENT 자동완성

## 1. sort

### a. 앞과 뒤 문자와 비교하기

def solution(words):
words.sort()

for idx in [0, len(words)-1]:
cases = -1 if idx > 0 else 1
for order in range(len(words[idx])):
try:
if words[idx][order] == words[idx+cases][order]:
else:
break
except:
break

for idx in range(1,len(words)-1):
left = 0
right = 0
for order in range(len(words[idx])):
try:
if words[idx-1][order] == words[idx][order]:
left += 1
else:
left += 1
break
except:
left += 1
break
for order in range(len(words[idx])):
try:
if words[idx][order] == words[idx+1][order]:
right += 1
else:
right += 1
break
except:
right += 1
break


### b. 맨앞 알파벳부터 모든 단어 비교하기(나의 풀이) def solution(words):

words.sort()

# make zero vector
counter_vector = []
for i in range(len(words)):
counter_vector.append([0 for j in range(len(words[i])+1)])

# fill counter_vector
word_stack = ['0']*MAX_COUNT
for i in range(len(words)):
fill_current_vector(i,words,counter_vector,word_stack)

#print(counter_vector)

for i in range(len(words)):

MAX_COUNT = 1000

def fill_current_vector(current_word,words,counter_vector,word_stack):
while(1):
current_step = counter_vector[current_word].index(0)
word_stack[current_step] = words[current_word][current_step]

for i in range(current_word,len(words)):
if current_step > len(words[i])-1 : break
if word_stack[current_step] == words[i][current_step] and counter_vector[i].index(0) == current_step :
counter_vector[i][current_step] = 1
else : break

# break condition 1
if counter_vector[current_word][-2] == 1 : break
# break condition 2, 3
if current_word == len(words)-1 : break
else:
if counter_vector[current_word+1][current_step] == 1 : pass
else : break


## 2. Trie

Trie구조를 사용하기 위한 python 기본 지식cur = dict()ccur = {}cur[‘c’] = ‘value’ cur[‘c’] = {‘num’ :1}print(cur) » {‘c’: {‘num’: 1}}

### a. def solution(words):
char_freq = {}
for word in words:
cur = char_freq
for char in word:
try:
cur[char]['num'] += 1
except:
cur[char] = {'num':1}
cur = cur[char]  # cursor 를 마지막에 갱신

res = 0

for word in words:
cur = char_freq
for char in word:
res += 1
if cur[char]['num'] == 1:
break
else:
cur = cur[char]
return res


### b.

def solution(words):
word_dict = build_dict(words)
total_num = 0
for word in words:
for i in range(len(word)):
if len(word_dict[word[:i+1]]) == 1:
total_num += i + 1
break
else:
total_num += len(word)