231112 - Trie 알고리즘(문자열), 투포인터 활용

[robert-min]

Trie 기본 구현

Trie Node

class TrieNode:
    def __init__(self, key, data=None):
        self.key = key  # 값으로 입력될 분자
        self.data = data    # 문자열의 종료를 알리는 flag
        self.children = defaultdict(TrieNode)   # 자식 노드를 저장

Trie 구현

• head를 빈노드로 구성
• insert 함수 : 트리를 생성하기 위한 함수로 입력된 무자를 하나씩 children에 저장, 문자열을 다 돌면 data에 문자열 저장
• search 함수 : 문자열이 존재하는지 여부를 리턴

• starts_with 함수 : prefix 단어로 시작하는 단어를 찾고 배열로 리턴하는 함수

  class Trie:
  
  def __init__(self):
      self.head = Node(None)
  
  def insert(self, string):
      current_node = self.head
  
      for char in string:
          if char not in current_node.children:
              current_node.children[char] = Node(char)
          current_node = current_node.children[char]
      current_node.data = string
  
  def search(self, string):
      current_node = self.head
  
      for char in string:
          if char in current_node.children:
              current_node = current_node.children[char]
          else:
              return False
  
      if current_node.data:
          return True
      else:
          return False
  
  def starts_with(self, prefix):
      current_node = self.head
      words = []
  
      for p in prefix:
          if p in current_node.children:
              current_node = current_node.children[p]
          else:
              return None
  
      current_node = [current_node]
      next_node = []
      while True:
          for node in current_node:
              if node.data:
                  words.append(node.data)
              next_node.extend(list(node.children.values()))
          if len(next_node) != 0:
              current_node = next_node
              next_node = []
          else:
              break
  
      return words

[robert-min]

트라이 활용

• https://school.programmers.co.kr/learn/courses/30/lessons/17685
• 문제
  • 기본 트라이에서 다른 단어에 없는 새로운 문자를 찾는 문제
  • 해당 문자를 찾도록 트라이에 저장된 문자의 참조 개수를 저장
  • 참조를 한 번만 한 경우가 우리가 찾는 문자임으로 해당 값으로 깊이를 출력

from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)

class TrieNode:
    def __init__(self, key, data=None):
        self.key = key  # 값으로 입력될 분자
        self.data = data    # 문자열의 종료를 알리는 flag
        self.children = defaultdict(TrieNode)   # 자식 노드를 저장
        self.n = 0  # 해당 노드가 방문한 횟수

    # 해당 노드를 방문한 횟수 n 저장
    def finalize(self):
        self.n = 1 if self.data else 0
        for char, node in self.children.items():
            self.n += node.finalize()
        return self.n

class Trie:
    def __init__(self):
        self.root = TrieNode(None)

    def insert(self, word):
        cur_node = self.root
        for char in word:
            if char not in cur_node.children:
                cur_node.children[char] = TrieNode(char)
            cur_node = cur_node.children[char]
        cur_node.data = word

    # 해당 노드를 방문한 횟수 n 저장
    def finalize(self):
        self.root.finalize()

    def search(self, word):
        depth = 0
        cur_node = self.root

        # 문자 하나씩 확인
        for char in word:
            if char in cur_node.children:
                cur_node = cur_node.children[char]
                depth += 1

                # 한번만 방문했다는 뜻은 해당 문자는 다른 문자에는 없는 단어로 찾으려는 값
                if cur_node.n == 1:
                    break

        return depth

def solution(words):
    """
    Return : 몇 개의 문자를 입력하면 되는지
    Params : words
    """
    answer = 0

    trie = Trie()

    for w in words:
        trie.insert(w)

    # 트라이 노드의 방문 횟수 저장
    trie.finalize()

    for w in words:
        answer += trie.search(w)

    return answer

[robert-min]

• https://school.programmers.co.kr/learn/courses/30/lessons/49995?language=python3

쿠키구입 - 투포인터 문제

• 풀이

  • 이전 시간 초과 풀이의 경우 리스트를 매번 계산했고 왼쪽과 오른쪽을 매 인덱스마다 확인했기 때문에 시간 초과가 발생
  • 아래 풀이는 인덱스를 기준으로 왼쪽, 오른쪽 중 합이 작은 것에 포인터를 이동하면서 계산

    
    def solution(cookie):
    """
    Return : 한 명의 아들에게 줄 수 있는 가장 많은 과자 수, 없으면 0

  • i ~ m = m+1, r

  """ answer = 0 N = len(cookie)

  중간의 기준점을 큰애 쿠키 i, 작은애 쿠키 i+1

  for i in range(N-1): left_sum, left_idx = cookie[i], i right_sum, right_idx = cookie[i+1], i+1

  while True:
      # 최댓값 갱신
      if left_sum == right_sum:
          answer = max(answer, left_sum)
  
      # 큰애가 작은애보다 더 적을 경우 쿠키를 더 준다.
      if left_idx > 0 and left_sum <= right_sum:
          left_idx -= 1
          left_sum += cookie[left_idx]
      # 작은애가 큰애보다 더 적을 경우 쿠키를 더준다.
      elif right_idx < N-1 and right_sum <= left_sum:
          right_idx += 1
          right_sum += cookie[right_idx]
      # 쿠키를 줄 수 없을 경우 종료
      else:
          break

  return answer

시간초과 풀이

def solution(cookie):
    """
    Return : 한 명의 아들에게 줄 수 있는 가장 많은 과자 수, 없으면 0
    - i ~ m = m+1, r 

    """
    answer = 0
    N = len(cookie)
    for left in range(N-1):
        right = left + 1

        # left
        sum_l = sum(cookie[:left+1])
        L_list = [sum_l]
        for i in range(left):
            sum_l -= cookie[i]
            L_list.append(sum_l)

        # right
        sum_r = sum(cookie[right:N])
        R_list = [sum_r]
        for j in range(N-1, right, -1):
            sum_r -= cookie[j]
            R_list.append(sum_r)

        if len(L_list) < len(R_list):
            for l in L_list:
                if l in R_list:
                    answer = max(answer, l)
        else:
            for r in R_list:
                if r in L_list:
                    answer = max(answer, r)

    return answer