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

28 Feb 2020 in Ubuntu / Language / Algorithm

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

1. sort

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

def solution(words):
    answer = 0
    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]:
                    answer += 1
                else:
                    answer += 1
                    break
            except:
                answer += 1
                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
        answer += max(left,right)
    return answer

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)

    # return answer
    answer = 0
    for i in range(len(words)):
        answer += sum(counter_vector[i])
    return answer




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)
            
    return total_num

def build_dict(words):
    d = {}
    for word in words:
        for i in range(len(word)):
            if not d.get(word[:i+1]):
                d[word[:i+1]] = [word]
            else:
                d[word[:i+1]].append(word)
    return d