1472. Design Browser History

1472. Design Browser History

 

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

 

 

https://youtu.be/i1G-kKnBu8k

 

이 문제는 브라우저의 방문 기록(뒤로가기, 앞으로가기) 기능을 구현하는 시뮬레이션 문제예요.
직접 클래스를 설계하고, 함수들을 정의해야 하죠.

---

🧠 문제 요약

브라우저에는 다음과 같은 기능이 있어요:

1. 처음 접속하는 홈페이지로 시작
2. visit(url): 새로운 페이지 방문 → 현재 위치에서 앞으로 갈 수 있는 기록은 모두 사라짐
3. back(steps): 뒤로 steps만큼 감 (더 못 가면 멈춤)
4. forward(steps): 앞으로 steps만큼 감 (더 못 가면 멈춤)
5. 각 함수는 현재 페이지의 URL을 리턴함

---

📦 예시 흐름

bh = BrowserHistory("leetcode.com")
bh.visit("google.com")     # 현재: google
bh.visit("facebook.com")   # 현재: facebook
bh.back(1)                 # 뒤로: google
bh.back(1)                 # 뒤로: leetcode
bh.forward(1)              # 앞으로: google
bh.visit("youtube.com")    # 방문: youtube (facebook 기록 사라짐)
bh.forward(2)              # 앞으로 못 감 → youtube

 

✅ 구현 아이디어

• history: URL들을 저장하는 리스트
• current: 현재 인덱스를 가리키는 포인터
• visit() 호출 시: current 이후를 자르고 새 URL 추가
• back() 호출 시: max(0, current - steps)
• forward() 호출 시: min(len(history) - 1, current + steps)

---

✅ 예시 코드

class BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.current = 0

    def visit(self, url: str) -> None:
        # 앞으로 가는 기록 제거하고 새 방문
        self.history = self.history[:self.current + 1]
        self.history.append(url)
        self.current += 1

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

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

 

🎯 시간 복잡도

• visit: O(1) (자르기 연산은 slicing이지만 적절하게 구현 시 효율적)
• back, forward: O(1)

최종 코드

🔁 왜 더블 링크드 리스트인가?

• 앞으로 가기(forward), **뒤로 가기(back)**를 모두 쉽게 하기 위해서예요.
• 단일 연결 리스트(single linked list)는 한 방향으로만 이동 가능하지만,
  이중 연결 리스트는 앞/뒤 포인터가 모두 있어서
  O(1) 시간에 뒤로도, 앞으로도 움직일 수 있어요.

🧱 구조 설계

class Node:
    - val (URL)
    - prev (이전 페이지)
    - next (다음 페이지)

 

✅ 코드 구현

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

class BrowserHistory:

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

    def visit(self, url: str) -> None:
        new_node = Node(url)
        self.curr.next = new_node
        new_node.prev = self.curr
        self.curr = new_node  # 앞으로 이동
        # 앞으로 가는 히스토리는 제거됨 (자동으로 덮어쓰기)
        # Python에서는 GC가 알아서 처리

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

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

 

🧪 예시 실행 흐름

bh = BrowserHistory("leetcode.com")  # 현재: leetcode
bh.visit("google.com")               # 현재: google
bh.visit("facebook.com")             # 현재: facebook
bh.back(1)                           # 현재: google
bh.forward(1)                        # 현재: facebook

---

🔍 요약

• 장점: 앞으로/뒤로 이동이 O(1)로 가능 (while 루프지만 노드 이동 자체는 빠름)
• 단점: 약간 더 많은 메모리를 사용 (prev 포인터)