List

이 저작물은 개발남노씨 - 코딩테스트 [ ALL IN ONE ] (opens in a new tab)을 참고하여 작성되었습니다.

Static List

Q

Two Sum

Two Sum On LeetCode (opens in a new tab)

n^2(완전 탐색)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
      for i in range(0, len(nums)) : 
        for j in range(i + 1, len(nums)) : 
          if( nums[i] + nums[j] == target ): return [i,j]

n(딕셔너리)

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    dict={}
    for i,n in enumerate(nums):
        if n in dict:
            return dict[n],i
        else:
            dict[target-n]=i

Linked List

Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다.
메모리 상에서는 비연속적으로 저장이 되며, 리스트의 크기가 정해져있지 않고 필요할 때마다 늘어날 수 있다.

class LinkedList(object) :
  def __init__(self) :
    self.head = None
  def append(self, value) : 
    new_node = Node(value)
    if self.head is None : 
      self.head = new_node
    else : 
      current = self.head
      while current.next is not None : 
        current = current.next
      current.next = new_node
    
  def get(self, index) : 
    current = self.head
    for _ in range(index) :
      if current.next is None : 
        break
      current = current.next
    return current.value
  def insert_at(self, index, value) : 
    current = self.head
    for _ in range(index - 1) : 
      current = current.next
    new_node = Node(value, current.next)
    # 현재 node의 next에 새 node를 연결
    current.next = new_node
  def remote_at(self, index) :
    current = self.head
    for _ in range(index - 1) : 
      current = current.next
    current.next = current.next.next

문제 1. Browser History

leetcode (opens in a new tab)

내 풀이

class Node :
  def __init__(self, value, prev = None, nextValue = None) : 
    self.prev = prev
    self.next = nextValue
    self.value = value
 
class BrowserHistory:
    def __init__(self, homepage: str):
      self.head = Node("leetcode.com")
 
    def visit(self, url: str) -> None:
      new_value = Node(url)
      if self.head is None : 
        self.head = new_value 
      else :
        new_value.prev = self.head
        self.head.next = new_value
        self.head = new_value
      return self.head
 
    def back(self, steps: int) -> str:
      for _ in range(steps) :
        if(self.head.prev is None) :
          break
        else : 
          self.head = self.head.prev
      return self.head.value
 
    def forward(self, steps: int) -> str:
      for _ in range(steps) :
        if(self.head.next is None) :
          break
        else :
          self.head = self.head.next
      return self.head.value

문제점

처음에 leetcode가 들어가 있지 않아서 __init__에서 self.head = None 으로 시작해서 오류가 발생했는데 디버깅이 불가능해서 그걸 찾는데 오래 걸렸다. 그리고 그로 인한 보일러 플레이트도 발생했다.

    # None인줄 알고 
    def visit(self, url: str) -> None:
      new_value = Node(url)
      if self.head is None : 
        self.head = new_value 
      else :
        new_value.prev = self.head
        self.head.next = new_value
        self.head = new_value
      return self.head

위 부분에서 존재히지도 않을 None 검사를 해주고 있다.

파이썬에선 인자를 전달해줄 땐 초기화 된 변수가 초기화 되지 않은 변수의 뒤로 가야지 오류가 발생하지 않는다.

class Node :
  # 처음에 이렇게 했더니 오류가 발생했다.
  def __init__(self, prev = None, nextValue = None, value) : 
    self.prev = prev
    self.next = nextValue
    self.value = value

강사님 풀이

class Node :
  def __init__(self, value, prev = None, next = None) : 
    self.prev = prev
    self.next = next
    self.value = value
 
class BrowserHistory:
    def __init__(self, homepage: str):
      self.head = Node(homepage)
 
    def visit(self, url: str) -> None:
      self.head.next = Node(value = url, prev = self.head)
      self.head = self.head.next
      return self.head
 
    def back(self, steps: int) -> str:
      while steps > 0 and self.head.prev != None :
        self.head = self.head.prev
        steps -= 1
      return self.head.value
 
 
    def forward(self, steps: int) -> str:
      while steps > 0 and self.head.next != None :
        self.head = self.head.next
        steps -= 1
      return self.head.value

파이썬 문법 큐와 스택