스파르타코딩 - 알고리즘 강의 3 주차 (ft.스택, 큐 , 해쉬)

스택

• # 스택 : 후입선출 ( LIFO )
  
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  class Stack:
      def __init__(self):
          self.head = None
  
  		# push 기능 구현
      def push(self, value):
          new_head = Node(value)
          new_head.next = self.head
          self.head = new_head
          return
  
      # pop 기능 구현
      def pop(self):
          if self.is_empty():
              return "Stack is Empty"
          delete_head = self.head
          self.head = self.head.next
          return delete_head
  
  		# peek 기능 구현
      def peek(self):
          if self.is_empty():
              return "Stack is Empty"
          return self.head.data
  
      # isEmpty 기능 구현
      def is_empty(self):
          return self.head is None
  
  stack = Stack()
  stack.push(3)
  print(stack.peek())
  stack.push(4)
  print(stack.peek())
  print(stack.pop().data)
  print(stack.peek())
  print(stack.is_empty())
  print(stack.pop().data)
  print(stack.is_empty())

  응용해보기

  • 레이더 문제

    top_heights = [6, 9, 5, 7, 4]
    
    def get_receiver_top_orders(heights):
        answer = [0] * len(heights)
        while heights:
            value = heights.pop() # 진행방향이 우측에서 좌측이기 때문에 pop
            for idx in range(len(heights) - 1, 0 , -1): # # 진행방향이 우측에서 좌측이기 때문에
                if heights[idx] > value : # value 보다 index 가 크다면
                    answer[len(heights)] = idx + 1 # answer 의 인덱스에 인덱스 값을 넣는다. 
                                                   # (이때 len(heights)인 이유는 pop 과정에서 길이가 줄어들기 때문)
                    break
        return answer
    
    print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!
    
    print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
    print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
    print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))

큐

• # 큐 : 선입선출 ( FIFO )
  
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  class Queue:
      def __init__(self):
          self.head = None
          self.tail = None
  
      # 삽입
      def enqueue(self, value):
          new_node = Node(value)
          if self.is_empty(): # 첫 노드일떄는 처음이자 끝
              self.head = new_node
              self.tail = new_node
              return
  
          self.tail.next = new_node
          self.tail = new_node
  
      # 삭제
      def dequeue(self):
          if self.is_empty():
              return "Queue is Empty"
  
          delete_head = self.head
          self.head = self.head.next
          return delete_head
  
      def peek(self): # 맨 앞을 봄..
          if self.is_empty():
              return "Queue is Empty"
          return self.head.data
  
      def is_empty(self):
          return self.head is None
  
  queue = Queue()
  queue.enqueue(3)
  print(queue.peek())
  queue.enqueue(4)
  print(queue.peek())
  queue.enqueue(5)
  print(queue.peek())
  queue.dequeue()
  print(queue.peek())
  print(queue.is_empty())
  queue.dequeue()
  print(queue.peek())
  queue.dequeue()
  print(queue.peek())

해쉬

• 딕셔너리 = 해쉬 테이블

  class Dict:
      def __int__(self):
          self.items = [None] * 8
  
      def put(self, key, value):
          index = hash(key) % len(self.items)
          self.items[index] = value
  
      def get(self, key):
          index = hash(key) % len(self.items)
          return self.items[index]
  
  my_dict = Dict()
  my_dict.put("test22", 3)
  print(my_dict.get("test"))

  링크드 튜플 & 링크드 딕셔너리

  class LinkedTuple:
      def __int__(self):
          self.items = list()
  
      def add(self, key, value):
          self.items.append((key, value))
  
      def get(self, key):
          for k, v in self.items:
              if key == k:
                  return v
  
  class LinkedDict:
      def __int__(self):
          self.items = []
          for i in range(8):
              self.items.append((LinkedTuple()))
  
      def put(self, key, value):
          index = hash(key) % len(self.items)
          self.items[index].add(key, value)
  
      def get(self, key, value):
          index = hash(key) % len(self.items)
          return self.items[index].get(key)

  응용해보기

  all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
  present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
  
  def get_absent_student(all_array, present_array):
      student_dict = {}
  		
  		# 모든 items
      for key in all_array: # 아무 값이나 넣어도 상관 없습니다! 여기서는 키가 중요한거니까요
          student_dict[key] = True
  
  		# 삭제할 items
      for key in present_array: # dict에서 key 를 하나씩 없앱니다
          del student_dict[key]
  
  		# 남은 items
      for key in student_dict.keys(): # key 중에 하나를 바로 반환합니다! 한 명 밖에 없으니 이렇게 해도 괜찮습니다.
          return key
  
  				# res.append(key)
          # data_join = ', '.join(res)
  
      # return data_join
  
  print(get_absent_student(all_students, present_students))
  
  print("정답 = 예지 / 현재 풀이 값 = ",get_absent_student(["류진","예지","채령","롯데","리아","유나"],["리아","류진","채령","유나"]))
  print("정답 = RM / 현재 풀이 값 = ",get_absent_student(["정국","진","뷔","슈가","지민","RM"],["뷔","정국","지민","진","슈가"]))