Browser History (browserHistory.py)

---

[문제]

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
• string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

[제한 사항]

• 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.

[입출력 예]

Input:

["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Output:

[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

[입출력 예에 대한 설명]

Explanation:

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.
browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"
browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

풀이

---

1차 시도

접근 방식

1. 문제를 읽어보니 브라우저의 방문 기록을 저장하는 알고리즘을 구현하는 문제같았다.
2. 먼저 생각난 자료구조는 스택이었다. 페이지를 방문할 때마다 스택에 해당 페이지를 push하고 뒤로 가기를 누르면 pop해서 현재 페이지를 보여주는 방식이 생각났다.
3. 하지만 스택으로 구현하면 forward 기능이 까다로울 것 같았고, 큐로 구현해도 마찬가지일 것 같았다.
4. forward, back 기능을 둘 다 수월하게 사용할 수 있는 자료구조는 링크드 리스트라고 생각되었다. 그리고 히스토리를 보존하면서 현재 보고있는 페이지를 앞으로, 뒤로 왔다갔다 하려면 양뱡향 링크드 리스트로 구현하는것이 맞겠다 싶었다.
5. 노드 클래스를 만들어 prev와 next필드가 있는 노드를 생성하고, 각 메서드가 하는 역할에 맞게 기능을 구현하였다.

코드

class Node:
    def __init__(self, val, prev = None, next = None):
        self.val = val
        self.prev = prev
        self.next = next

class BrowserHistory:

    def __init__(self, homepage: str):
        self.head = Node(homepage)
        self.curr = self.head
        self.tail = self.head

    def visit(self, url: str) -> None:
        self.curr.next = Node(url, self.curr)
        self.curr = self.curr.next
        self.tail = self.curr

    def back(self, steps: int) -> str:
        while not(steps == 0 or self.curr.prev == None):
            self.curr = self.curr.prev
            steps -= 1
        return self.curr.val

    def forward(self, steps: int) -> str:
        while not(steps == 0 or self.curr.next == None):
            self.curr = self.curr.next
            steps -= 1
        return self.curr.val

결과

배운점

• 문제를 천천히 잘 읽어보자. back과 forward에 return값이 있다는 것을 대충 읽고 문제만 풀었을 때 결과값이 계속 전부 null로 나와서 한참을 헤맸는데, 알고보니 back과 forward에 return을 안하고 있었다..
• 링크드 리스트로 현재 가리키는 노드를 이동시키거나 노드를 추가하거나 삭제하거나 할 때 각 변수들에 새로운 값을 할당하게 되는데, 이 때 순서를 잘 고려해야 할 것 같다. 각 변수가 새로운 값이 할당되고 나면 해당 변수의 이전값을 참조해야 하는 연산이 나중에 나올때 문제가 될 수 있기 때문이다.