[알고리즘] Leetcode-design-browser-history 파이썬 문제 풀이

문제 링크

문제

browserHistory를 구현하는 문제이다.

1. BrowserHistory(homepage)를 실행하면 homepage 주소를 베이스로 BrowserHistory가 생성된다.
2. visit(url)을 실행하면 url 주소가 마지막에 추가된다.
3. back(steps)를 실행하면 steps의 수만큼 주소를 뒤로가기 하면 된다. (만약 뒤로가다가 homepage까지 간다면 더이상 뒤로가기를 하지 않는다.)
4. forward(steps)를 실행하면 steps의 수만큼 주소를 앞으로 가기 하면 된다. (만약 앞으로 가다가 더 이상 방문한 기록이 없으면 더이상 앞으로 가기를 하지 않는다.)

입출력 예시

입출력을 잘 보게되면 visit일 때는 출력이 null이고, back, forward를 사용하면 step만큼 이동한 후의 주소값이 출력된다.

조건

시간복잡도에 직접 영향을 미치는 요소는 steps의 수와 마지막 줄의 총 visit, back, forward는 5000을 넘지 않는다는 문장이다. 유의하면서 구현해보도록 하자.

풀이 - Double Linkedlist 사용

class Page(object):
    def __init__(self, value = 0, prev = None, next = None):
        self.value = value
        self.prev = prev
        self.next = next
        
class BrowserHistory(object):
    def __init__(self, homepage):
        self.current = Page(value=homepage)
        
    def visit(self, url):
        self.current.next = Page(value=url, prev=self.current)
        self.current = self.current.next
        return None
        
    def back(self, steps):
        while steps > 0 and self.current.prev != None:
            steps -= 1
            self.current = self.current.prev
        return self.current.value
        
    def forward(self, steps):
        while steps > 0 and self.current.next != None:
            steps -= 1
            self.current = self.current.next
        return self.current.value

우선 처음 풀이방법은 Double Linkedlist를 사용했다. 앞으로가기, 뒤로가기가 모두 있으니 Double이 확실히 편하긴 하다.
앞, 뒤 Page의 주소를 담고 있도록 Page class를 만들어 주었고, 이를 활용해 BrowserHistory를 구현해주었다.
history에는 current를 정의해주고 visit, back, forward의 상황에 따라 current가 옮겨가면서 현재 페이지를 가르키도록 구현했다.

풀이 - Array list

class BrowserHistory(object):
    def __init__(self, homepage):
        self.arr = [homepage]
        self.index = 0
        
    def visit(self, url):
        self.index += 1
        self.arr = self.arr[0:self.index]
        self.arr.append(url)
        return None
    
    def back(self, steps):
        self.index -= steps
        if self.index < 0:
            self.index = 0
        return self.arr[self.index]
    
    def forward(self, steps):
        self.index += steps
        if self.index > len(self.arr) - 1:
            self.index = len(self.arr) - 1
        return self.arr[self.index]

python의 기본 list(Array list)를 사용해서도 풀어봤다.
visit가 현재페이지 뒤에 새로운 페이지를 넣어줘야하는데 어짜피 앞의 방문기록만 필요하고 뒤는 다 사라져야되기 때문에 슬라이스를 활용해 0부터 현재 인덱스까지만 잘라주고 뒤에 url 페이지를 append 해주도록 했다.
이번 문제는 다른 까다로운 조건이 없다보니 Array list의 index를 활용해 current를 표기해주는 방법도 시간복잡도를 크게 신경쓰지 않아도 풀리는 문제이다.