[programmers] 가사찾기_binary search, trie

블럭 이동하기

link

내 풀이

• 방식 : binary search
• 물음표를 제외한 문자열 binary search로 찾기
• python에서는 여러 문자열에 대한 비교연산사 가능함
• 같은 길이에 대한 sorting은 한번만 할 수 있도록 dp로 구현

📰code

from collections import defaultdict

def solution(words, queries):
    
    answer = []
    words_dict = defaultdict(list)
    words_dict_reverse = defaultdict(list)
    
    # word 길이에 따른 hash table 구성(정방향, 반대방향)
    for word in words:
        words_dict[len(word)].append(word)
        words_dict_reverse[len(word)].append(word[::-1])
    
    def binary_search(arr,i,q,l,r,d):
        mid = int((l+r)/2)
        if r <= l:
            return l
        elif arr[mid][:i]<q[:i]:
            return binary_search(arr,i,q,mid+1,r,d)
        elif arr[mid][:i]>q[:i]:
            return binary_search(arr,i,q,l,mid,d)
        else : # arr[mid]==x
            if d == 'left':
                return binary_search(arr,i,q,l,mid,d)
            else : # right
                return binary_search(arr,i,q,mid+1,r,d)      
    
    def find_p(words_list,search_dir,q):
        length = len(words_list[0])
        # 물음표 위치 확인
        for i in range(length):
            if q[i] =='?': break
        left, right = 0,len(words_list)
        # 물음표를 제외한 문자열 만큼 binary search로 좌표확인
        left = binary_search(words_list,i,q,left, right, 'left')
        right = binary_search(words_list,i,q,left, right, 'right')
        return right - left

    # wordlist 정렬 한번만 하도록 dp 구성
    dp_rev = [0]*100001
    dp = [0]*100001
    
    for q in queries:
        q_l=len(q)
        # 해당 길이에 대한 단어 없음
        if words_dict[q_l] ==[]:
            answer.append(0)
        # '?'로 시작할 경우 reverse로 찾기
        elif q.startswith('?'):
            search_dir = 'back'
            if dp_rev[q_l] ==0 :
                words_dict_reverse[q_l] = sorted(words_dict_reverse[q_l])
                dp_rev[q_l]=1
            words_list = words_dict_reverse[q_l]
            answer.append(find_p(words_list,search_dir,q[::-1]))
        # '?'로 끝날 경우 정방향으로 찾기 
        else :
            search_dir = 'front'
            if dp[q_l] == 0 :
                words_dict[q_l] = sorted(words_dict[q_l])
                dp[q_l]=1
            words_list = words_dict[q_l]
            answer.append(find_p(words_list,search_dir,q))
    
    return answer

1트 code _ NG

📰code

from collections import defaultdict

def solution(words, queries):
    
    answer = []
    words_dict = defaultdict(list)
    
    for word in words:
        words_dict[len(word)].append(word)
    
    ans_memo = defaultdict(list)
    
    def binary_search(arr,i,q,l,r,d):
        mid = int((l+r)/2)
        if r <= l:
            return l
        elif ord(arr[mid][i])<ord(q[i]): # 파이썬에서는 ord 사용안해도 여러 문자열 비교 가능
            return binary_search(arr,i,q,mid+1,r,d)
        elif ord(arr[mid][i])>ord(q[i]):
            return binary_search(arr,i,q,l,mid,d)
        else : # arr[mid]==x
            if d == 'left':
                return binary_search(arr,i,q,l,mid,d)
            else : # right
                return binary_search(arr,i,q,mid+1,r,d)      
    
    def find_p(words_list,search_dir,q):
        length = len(words_list[0])
        if search_dir == 'front':
            for i in range(length):
                left, right = 0,len(words_list)
                if q[i] =='?':
                    return right - left
                temp_list = sorted(words_list[left:right], key = lambda x:x[i]) #지속적으로 정렬이 필요함.. 이 부분 개선 필요
                left = binary_search(temp_list,i,q,left, right, 'left')
                right = binary_search(temp_list,i,q,left, right, 'right')
                words_list = temp_list[left:right]
        else : # search_dir == 'front':
            for i in range(length-1,-1,-1):
                left, right = 0,len(words_list)
                if q[i] =='?':
                    return right - left
                temp_list = sorted(words_list[left:right], key = lambda x:x[i])
                left = binary_search(temp_list,i,q,left, right, 'left')
                right = binary_search(temp_list,i,q,left, right, 'right')
                words_list = temp_list[left:right]
        
    for q in queries:
        if words_dict[len(q)] ==[]:
            answer.append(0)
        elif q.startswith('?'):
            search_dir = 'back'
            words_list = words_dict[len(q)]
            answer.append(find_p(words_list,search_dir,q))
        else :
            search_dir = 'front'
            words_list = words_dict[len(q)]
            answer.append(find_p(words_list,search_dir,q))
    
    return answer

다른 사람 풀이_Trie

📰code

class Node:
    def __init__(self, data):
        self.data = data
        self.count = 0
        self.child = {} # dictionary 형태로 Tree 생성

class Trie:
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        cur = self.head
        cur.count += 1

        for c in string:
            if c not in cur.child:
                cur.child[c] = Node(c) # 새로운 Node에 data, count, child로 업데이트
            cur = cur.child[c]
            cur.count += 1

    def count(self, prefix):
        cur = self.head

        for c in prefix:
            if c not in cur.child:
                return 0
            cur = cur.child[c]

        return cur.count


def solution(words, queries):
    answer = []

    tries = create_trie(words)
    reversed_tries = create_trie(words, is_reversed = True)
    for query in queries:
        answer.append(count_matched_word(tries, reversed_tries, query))

    return answer


def create_trie(words, is_reversed = False):
    trie_dic = {i: Trie() for i in range(1, 10001)}

    for word in words:
        if is_reversed:
            word = word[::-1]
        trie_dic[len(word)].insert(word)

    return trie_dic


def count_matched_word(tries, reversed_tries, query):
    no_mark_query = query.replace('?', '')

    if query[0] == '?':
        return reversed_tries[len(query)].count(no_mark_query[::-1])
    else:
        return tries[len(query)].count(no_mark_query)

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡