[LeetCode] 1472. Design Browser History

1. 문제 이해

문제 해석

브라우저 하나의 탭으로 homepage에서 시작하여 다른 url에 방문할 수 있고,
입력 받은 stpes 수 만큼 뒤로 가거나 앞으로 갈 수 있도록 구현한다.

• BrowserHistory(string homepage): 입력받은 string homepage로 인스턴스 객체를 초기화한다.
• void visit(string url): 가장 최근 페이지에서 입력받은 string url을 방문하고 앞으로가기 스택을 모두 비운다.
• string back(int steps)
  • 입력받은 steps 수 만큼 뒤로가기 한다.
  • 만약 입력 받은 steps > 뒤로가기 스택 수(x)인 경우, 스택 수(x) 만큼만 뒤로가기 한다.
  • 입력 받은 steps 만큼 최대한 뒤로가기 후 마주하는 url을 리턴한다.
• String forward(int steps)
  • 입력받은 steps 수 만큼 앞으로가기 한다.
  • 만약 입력 받은 steps > 앞으로가기 스택 수(x)인 경우, 스택 수(x) 만큼만 앞으로가기 한다.
  • 입력 받은 steps 만큼 최대한 앞으로가기 후 마주하는 url 리턴한다.

제약 조건 해석

• 1 <= homepage.length <= 20,
  1 <= url.length <= 20,
  1 <= steps <= 100
• homepage and url consist of '.' or lower case English letters.
• At most 5000 calls will be made to visit, back, and forward.

시간복잡도로 측정될 실질적인 n은 steps이지만,
100 이하로 제한되어 있으므로 시간복잡도에 따른 구현 제약은 딱히 없어 보인다.
다만 visit, back, forward 각각 최대 5,000번 호출이 가능하다는 것인지,
아니면 세 작업의 총 호출 수를 말하는 것인지 헷갈렸다.
문맥상 세 작업의 호출수 총합이 최대 5,000이라고 말하는 것 같다.
그렇다면 극단적으로 최악의 경우를 생각해본다면
visit 횟수 100번 후 back(100)와 forward(100) 번갈아가면서 총 4900번
호출되었을 때, 4900 * 100(최대 steps 수) -> 490,000 이므로 문제는 없을 것 같다.

2. 접근 방법

먼저 직관적으로 생각하기

- 생성자 함수
  1. homepage를 입력받은 object로 초기화해준다.
  2. 객체 변수(currentPage, backStack, forwardStack)를 선언한다.
- visit
  1. currentPage를 backStack 상단에 올린다.
  2. currentPage에 url을 할당한다.
  3. forwardStack을 비운다.
- back
  1. currentPage를 forwardStack 상단에 올린다.
  2. backStack 최상단 요소를 제거하고 currentPage에 할당한다. 
- forward
  1. currentPage를 backStack 상단에 올린다.
  2. forwardStack 최상단 요소를 제거하고 currentPage에 할당한다.

Array를 활용해서 뒤로가기(앞으로가기) 2개의 Stack을 만들어 구현하는 방법이 먼저 떠올랐다.
하지만 Linked list를 활용한 구현 방법은 떠오르지 않았다.

활용한 자료구조 & 알고리즘

LeetCode Editorial의 Doubly Linked list를 활용한 Soultion을 참고했다.

1. 먼저 Doubly Linked list Node로 사용할 class를 정의한다.

   • url string을 저장할 변수 선언한다.
   • prev, next node를 가리키는 pointers 선언한다.

2. BrowserHistory class를 정의한다.

   • 클래스 변수 초기화
     • Head node를 가리키는 변수에 DLLNode의instance를 할당한다.
     • Current URL node를 가리키는 current 변수 선언한다.
   • visit(url) method 구현
     1. 입력된 url을 기반으로 새로운 node를 생성
     2. current node의 next가 새로운 node를 가리키도록 한다.
     3. 새로운 node의 prev가 current node를 가리키도록 한다.
        (2~3 과정을 통해, current node의 next nodes와의 연결을 끊고 새로운 node를 삽입한다.)
     4. 그 후 current로 새로운 node를 가리킨다.
   • back(steps) method 구현
     1. steps 카운트가 1 이상이고 current의 prev 있다면, current pointer를 왼쪽으로 이동한다.
     2. 그 후 변경된 current URL을 리턴한다.
   • forward(steps) method 구현
     • back(steps) method의 반대로 동작하도록 구현한다.

3. 코드 설계 및 구현

작성한 코드

# 1. 먼저 Doubly Linked list Node로 사용할 class를 정의한다.
class DLLNode:
    def __init__(self, url):
        # url string을 저장할 변수 선언한다.
        self.data = url
        # prev, next node를 가리키는 pointers 선언한다.
        self.prev, self.next = None, None

# 2. BrowserHistory class를 정의한다.
class BrowserHistory:

    # 클래스 변수 초기화
    def __init__(self, homepage):
        """
        :type homepage: str
        """
        # Head node를 가리키는 변수에 DLLNode의 instance를 할당한다. 
        self.head = DLLNode(homepage)
        # Current URL node를 가리키는 current 변수 선언한다.
        self.current = self.head

    def visit(self, url):
        """
        :type url: str
        :rtype: None
        """
        # 1. 입력된 url을 기반으로 새로운 node를 생성
        new_node = DLLNode(url)
        # 2. current node의 next가 새로운 node를 가리키도록 한다.
        self.current.next = new_node
        # 3. 새로운 node의 prev가 current node를 가리키도록 한다.
        # (2~3 과정을 통해, current node의 next nodes와의 연결을 끊고 새로운 node를 삽입한다.)
        new_node.prev = self.current
        # 4. 그 후 current로 새로운 node를 가리킨다.
        self.current = new_node

    def back(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        # 1. steps 카운트가 1 이상이고 current의 prev 있다면, current pointer를 왼쪽으로 이동한다.
        while steps and self.current.prev:
            self.current = self.current.prev
            steps -= 1
        # 2. 그 후 변경된 current URL을 리턴한다.
        return self.current.data

    def forward(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        while steps and self.current.next:
            self.current = self.current.next
            steps -= 1
        return self.current.data

• visit(url) method에서는 새로운 node를 추가하고 url을 저장하면서 l(url의 length) 만큼 메모리 할당이 필요하므로 O(l)의 복잡도를 갖는다.
  (current pointer를 새로 생성한 node로 가리키는 것은 O(1))
• back(url), forward(url) method의 시간복잡도는 O(min(m,n))이다.

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