[LeetCode] 1472. Design Browser History

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

Design Browser History - LeetCode

Algorithm

• double link list , stack
• 더블 링크 리스트는 노드(prev,val,next) 초기화후, cur 포인터를 이용해 순회한다.
• stack은 배열 [], cur pointer,len을 풀이에 사용해 접근한다. 이때 len은 history의 진짜 총 길이이다.i는 말그대로 현재위치를 가리키는 포인터이다.

---

Python

더블 링크 리스트

class ListNode:
    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.cur = ListNode(homepage) # cur pointer

    # O(1)
    def visit(self, url: str) -> None:
        self.cur.next = ListNode(url, self.cur) #새 노드 생성 및 연결
        self.cur = self.cur.next # cur pointer 이동

    # O(n)
    def back(self, steps: int) -> str:
        while self.cur.prev and steps > 0:
            self.cur = self.cur.prev
            steps -= 1
        return self.cur.val

    # O(n)
    def forward(self, steps: int) -> str:
        while self.cur.next and steps > 0:
            self.cur = self.cur.next
            steps -= 1
        return self.cur.val

 

스택

class BrowserHistory:

    def __init__(self, homepage: str):
        self.i = 0 # curr pointer
        self.len = 1
        self.history = [homepage]

    def visit(self, url: str) -> None:
        if (len(self.history)-1) < (self.i + 1): # 맨 끝 인덱스 < "삽입할 다음페이지" 인덱스
            self.history.append(url) # 삽입
        else:
            self.history[self.i+1] = url
        self.i += 1
        self.len = self.i + 1

    def back(self, steps: int) -> str:
        self.i = max(self.i-steps, 0)
        return self.history[self.i]

    def forward(self, steps: int) -> str:
        self.i = min(self.i+steps,self.len-1)
        return self.history[self.i]


# 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)

Java

더블 링크 리스트

class ListNode{
    ListNode prev;
    String url;
    ListNode next;
    public ListNode(String url){
        this.url = url;
        prev = next = null;
    }
}

class BrowserHistory {
    ListNode head;
    ListNode cur;

    public BrowserHistory(String homepage) {
        head = new ListNode(homepage); // head 생성
        cur = head; // 포인터 초기화
    }
    
    public void visit(String url) {
        cur.next = new ListNode(url); // -> 연결
        cur.next.prev = cur; // <- 연결
        cur = cur.next; // 포인터 이동
    }
    
    public String back(int steps) {
        while(steps > 0 && cur.prev!=null){
            cur = cur.prev;
            steps-=1;
        }
        return cur.url;
    }
    
    public String forward(int steps) {
        while(steps > 0 && cur.next!=null){
            cur = cur.next;
            steps-=1;
        }
        return cur.url;
    }
}

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

 

스택

import java.util.ArrayList;
import java.util.List;

class BrowserHistory {
    private int i; // curr pointer
    private int len;
    private List<String> history;

    public BrowserHistory(String homepage) {
        this.i = 0;
        this.len = 1;
        this.history = new ArrayList<>();
        this.history.add(homepage);
    }
    
    public void visit(String url) {
        if(this.history.size()-1 < this.i + 1){
            this.history.add(url);
        }else{
            this.history.set(this.i+1,url);
        }
        this.i += 1;
        this.len = this.i + 1;
    }
    
    public String back(int steps) {
        this.i = Math.max(this.i - steps, 0);
        return this.history.get(this.i);
    }
    
    public String forward(int steps) {
        this.i = Math.min(this.i + steps, this.len-1);
        return this.history.get(this.i);
    }
}

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