[LeetCode] 1472. Design Browser History

말하는 감자·2024년 11월 5일
Array Listdata structureleetcodelinked listpythonstack리스트링크드 리스트배열스택자료구조코딩테스트코딩테스트 준비파이썬
1

LeetCode

목록 보기
2/32
post-thumbnail

논문 작업으로 인해 정말 오랜만에 돌아왔습니다. 내년 상반기 취뽀를 위해 다시 시작해야겠죠? 오늘 문제는 다양한 선형 자료구조들을 활용해서 풀 수 있는 문제입니다. 살펴볼까요?

1. 오늘의 학습 키워드

  • 선형 자료구조
    • array list
    • linked list
    • stack

2. 문제: 1472. Design Browser History

1472. Design Browser History

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.

Example:

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"

Constraints:

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

3. 문제 풀이

Browser History 문제는 브라우저의 방문 기록을 다루는 문제로, 다양한 선형 자료구조를 활용하여 해결할 수 있는것처럼 보입니다. 왜냐하면 forward, back 와 같이 앞, 뒤로 만 이동하기 때문입니다. 그럼 문제를 조금 더 자세하게 살펴보겠습니다.

Step1. 문제 이해하기

  • Input:
    • 초기 페이지인 homepage가 주어집니다.
    • visit(url)을 호출하면 새 URL을 방문하고, 현재 이후의 모든 forward 기록이 삭제됩니다.
    • back(steps)는 최대 steps만큼 뒤로 이동하고, forward(steps)는 최대 steps만큼 앞으로 이동합니다.
    • 만약 전체 길이(이동한 경로)가 steps 보다 짧다면, 처음이나 끝으로 돌아갑니다.
  • Output:
    • visit(url) 은 반환 값이 없습니다.
    • back과 forward는 이동 후의 URL을 반환해야 합니다.
  • Constraints:
    • 각 URL의 길이는 최대 20자입니다.
    • steps 은 최대 100번입니다.
    • visit, back, forward의 호출 횟수는 최대 5,000번입니다.

URL의 길이는 코드의 시간 복잡도에 영향을 주지 않습니다. 얼만큼 앞으로, 뒤로 이동하는지 결정하는 steps 이 시간복잡도에 영향을 미칠것으로 예상됩니다.

Step2. 접근 방법

  • 문제 단순화 및 자료구조 선택:
    • 방문 시 이전 forward 기록이 초기화되는 구조를 생각해 보면, 방문 시마다 특정 자료구조를 초기화해야 하는 것을 알 수 있습니다.
    • Array list일 경우 해당 index에 해당하는 값을 변환하면 되고, Linked list일 경우 연결되어있는 노드를 끊고 새로운 노드로 연결하면 됩니다.
    • Linked List: 노드 간 연결을 통해 back과 forward가 빠르게 동작할 수 있습니다.
    • Array List: 인덱스를 기반으로 back과 forward를 관리할 수 있습니다.
    • Stack: back과 forward 각각을 스택으로 관리하여 효율적으로 이동할 수 있습니다.

Linked List 풀이

코드 설계

  • Doubly Linked List로 현재 페이지 위치를 노드로 설정하고 back과 forward 시 이전과 다음 노드로 이동할 수 있도록 합니다.
####################### 1. Linked List 풀이 ####################### 

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

class BrowserHistory(object):
    
    def __init__(self,homepage):
        
        self.current = Node(val=homepage)
        
    def visit(self,url): # O(1)
        """
        :type url: str
        :rtype: None
        """
        
        self.current.next = Node(val=url,prev=self.current)
        self.current = self.current.next
        return None
    
    def back(self,steps): # Time Complexity: O(min(steps, d)) -> O(n), where d is the distance to the first page.
        """
        :type steps: int
        :rtype: str
        """
        while steps > 0 and self.current.prev != None:
            steps -= 1
            self.current = self.current.prev
        return self.current.val
    
    def forward(self,steps): # Time Complexity: O(min(steps, d)) -> O(n), where d is the distance to the end page.
        """
        :type steps: int
        "rtype: str
        """
        while steps > 0 and self.current.next != None:
            steps -= 1
            self.current = self.current.next
        return self.current.val
    
####################### 1. Linked List 풀이 #######################

시간 복잡도

  • visit 는 O(1), back, forward는 O(min(steps, d)) —> O(n)로, steps가 작을수록 빠르게 동작합니다.

결과

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

Array List 풀이

코드 설계

  • Array List를 사용하여 back과 forward를 현재 인덱스로 이동하여 관리합니다.
####################### 2. Array List 풀이 ####################### 
class BrowserHistory(object):
    def __init__(self,homepage):
        
        self.list = [homepage]
        self.current_idx = 0
    
    def visit(self,url): # O(n)
        """
        :type url: str
        :rtype: None
        """
        while self.current_idx != len(self.list) - 1:
            self.list.pop()
        
        self.list.append(url)
        self.current_idx += 1
        
        return None
    
    def back(self,steps): # O(1)
        """ 
        :type steps: int
        :rtype: str
        """
        if self.current_idx < steps:
            self.current_idx = 0
        else:
            self.current_idx -= steps
        
        return self.list[self.current_idx]
    
    def forward(self,steps): # O(1)
        """
        :type steps: int
        "rtype: str
        """
        if self.current_idx + steps > len(self.list) - 1:
            self.current_idx = len(self.list) - 1
        else:
            self.current_idx += steps
        
        return self.list[self.current_idx]
    
####################### 2. Array List 풀이 #######################

시간 복잡도

  • visit은 방문 시 forward 기록을 지우므로 O(n)의 시간 복잡도가 발생합니다.
  • back과 forward는 인덱스를 조정하므로 O(1)로 수행됩니다.

결과

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

Stack 풀이

코드 설계

  • back과 forward 스택을 사용하여 현재 페이지를 관리하며, 새로운 URL을 방문할 때는 forward 스택을 초기화합니다.
  • 이때 스택을 사용하는 이유는 LIFO(Last In, First Out) 원리 때문입니다. 스택은 가장 나중에 들어온 값부터 꺼내게 되므로, back 동작은 가장 최근에 방문한 사이트부터 순차적으로 돌아가는 과정과 일치합니다. 즉, back을 수행하면 최근 방문했던 사이트부터 차례로 방문할 수 있기 때문에 스택 자료구조가 적합합니다.
  • forward 동작도 스택을 활용하여 구현할 수 있습니다. back을 수행할 때마다 현재 페이지가 forward 스택에 쌓이므로, 다시 앞으로 이동할 때는 forward 스택에서 가장 최근에 추가된 페이지를 꺼내와 이동할 수 있습니다. 따라서 forward는 back을 수행하면서 잠시 보관한 페이지들을 순서대로 다시 꺼내면서 앞쪽으로 이동할 수 있게 됩니다. 이렇게 하면 forward 스택에서도 LIFO 구조를 이용해 최근의 방문 기록을 효율적으로 관리할 수 있습니다.
######################### 3. Stack 풀이 ######################### 
class BrowserHistory(object):
    def __init__(self,homepage):
        self.current = homepage
        self.back_stack = []
        self.forward_stack = []
        
    def visit(self,url): # O(1)
        """
        :type url: str
        :rtype: None
        """
        self.back_stack.append(self.current)
        
        self.current = url
        
        self.forward_stack = []
        
    def back(self,steps): # O(steps)
        
        while steps > 0 and self.back_stack:
            self.forward_stack.append(self.current)
            
            self.current = self.back_stack.pop()
            steps -= 1
            
        return self.current
     
    def forward(self,steps): # O(steps)
        
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.current)
            
            self.current = self.forward_stack.pop()
            steps -= 1
        
        return self.current
    
######################### 3. Stack 풀이 #########################

시간복잡도

  • visit, back, forward가 각각 O(1), O(steps)로 수행되며, 모든 이동이 steps만큼 반복됩니다.

결과

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

4. 마무리

이번 문제는 브라우저 방문 기록 관리라는 친숙한 상황을 다양한 자료구조로 풀어보며, 각 구조의 특징과 활용법을 확인할 수 있었습니다.

  1. Stack: back과 forward를 스택으로 관리하여 LIFO 구조를 활용해 가장 최근 기록을 효과적으로 관리할 수 있었습니다.
  2. Array List: 방문 기록을 인덱스를 통해 관리하며, back과 forward 이동이 빠른 장점이 있습니다.
  3. Linked List: 양방향 연결 리스트를 통해 효율적으로 앞뒤로 이동하며 방문 기록을 유지할 수 있었습니다.

이 문제를 통해 각 자료구조의 장단점을 비교하고, 적합한 구조를 선택하는 중요성을 다시 한 번 체감할 수 있었습니다. 브라우저 방문 기록과 같은 문제는 일상에서 자주 접할 수 있는 시나리오인 만큼, 자료구조 선택이 코드의 효율성을 어떻게 높이는지 이해하는 데 매우 유익한 연습이었습니다. 문제의 Constraint(제약 조건)에 따라 어떤 자료구조를 활용하고 선택해야하는지 도움이 된 문제라고 생각합니다.

전체 코드는 다음 링크에서 확인하실 수 있습니다.

읽어주셔서 감사합니다!!

더 나은 개발자가 될거야!

profile
말하는 감자
https://potato9703.tistory.com/ 로 이전합니다
이전 포스트

LeetCode 문제 TIL START

다음 포스트

[LeetCode] 1. Two Sum

0개의 댓글