[leetcode/1472번] BrowserHistory

문제 링크

https://leetcode.com/problems/design-browser-history/

Design Browser History - LeetCode

 

문제에서 주어진 코드 베이스 라인은 다음과 같다.

class BrowserHistory(object):

    def __init__(self, homepage):
        """
        :type homepage: str
        """
        

    def visit(self, url):
        """
        :type url: str
        :rtype: None
        """
        

    def back(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        

    def forward(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        


# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

 

해결 방법(python)

문제를 읽어보면 자료를 추가하고 이동하는 과정에서 선형적인 자료구조가 필요함을 알 수 있다. 

따라서 파이썬의 List 자료형 중 ArrayList, LinkedList 를 고려해 볼 수 있다. 

ArrayList를 사용할 경우 back과 forward를 구현할 때 시간복잡도가 O(1)로 편하나 back과 foward를 거친 후 visit()을 새로 호출할 때의 시간복잡도가 O(n)이 되므로 전체적으로 O(n)의 시간 복잡도를 가진다.

LinkedList를 사용할 경우 visit() 호출 시 시간복잡도가 O(1)이나 back과 forward 구현 시 O(n)의 시간 복잡도를 가질 것이므로 전체적으로 O(n)의 시간 복잡도를 가진다. 따라서 둘 중 어떤 자료구조를 사용하든 실행시의 큰 차이는 없을 것으로 보인다. 

아래는 (double)LinkedList로 구현한 파이썬 코드이다.

# doublelinkedList
class doubleNode(object):
  def __init__(self, val = 0, pre = None, next = None):
    self.val = val
    self.pre = pre
    self.next = next

class BrowserHistory(object):
  def __init__(self,browser):
    self.head = self.current = doubleNode(val = browser)
  def visit(self,browser):
    self.current.next = doubleNode(val = browser,pre = self.current)
    self.current = self.current.next
    return None
  def pre(self,steps):
    for _ in range(steps):
      if(self.current.pre != None):
        self.current = self.current.pre
      else:
        pass
    return self.current.val
  def next(self,steps):
    for _ in range(steps):
      if(self.current.next != None):
        self.current = self.current.next
      else:
        pass
    return self.current.val

# 구현 결과 확인용
br = BrowserHistory('google.com')
print(br.visit('1.com'))
print(br.visit('2.com'))
print(br.visit('3.com'))
print(br.visit('4.com'))
print(br.visit('5.com'))
print(br.pre(3))
print(br.pre(3))
print(br.next(4))
print(br.next(4))

 

 

연결리스트로 구현한 결과화면

정상적으로 실행됨을 알 수 있다.