Design Browser History

Linked List 구현

1. 문제 이해

1-1. 예시

우리가 흔히 작동 시키는 url 방문, 앞으로가기, 뒤로가기를 작동시키면 된다. 게임중에서 시장에 가면을 생각하자

input과 예시를 같이 보면 이해가 쉽다

1. 리트코드 접속 (홈페이지)

2. 구글 접속 ( 리트코드 -> 구글)

3. 페이스북 접속 ( 리트코드 -> 구글 -> 페이스북)

4. 유튜브 접속 (리트코드 -> 구글 -> 페이스북 -> 유튜브)

여기 까지는 모두 None을 반환한다 즉 반환값이 없다

5. 뒤로가기 한번 (유튜브 전 페이지인 페이스북 접속)

페이스북 주소 반환

6. 뒤로가기 한번 (페이스북 전 페이지인 구글 접속)

구글 주소 반환

7. 앞으로 가기 한번 (구글 앞 페이지인 페이스북 접속)

페이스북 주소 반환

8. 링크드인 접속 (리트코드 -> 구글 -> 페이스북 -> 링크드인)

앞에 있는 url은 모두 삭제된다고 조건에 나와있고 현재 페이지가 페이스북인 상태에서 다른 주소로 접속 했으니까 원래 히스토리인 유튜브는 사라지고 링크드인이 들어간다 반환값은 없다

9. 앞으로가기 두번(링크드인에 앞은 아무것도 없기 때문에 이런경우 현재 히스토리에 끝으로 간다)

링크드인 주소 반환

10. 뒤로가기 두번 (링크드인에서 두번 뒤로가면 구글 페이지 접속)

구글 주소 반환

10. 뒤로가기 7번(앞으로 가기와 마찬가지로 7번까지 갈 히스토리가 없기 때문에 가장 처음으로 간다)

리트코드 반환

1-2. 제약조건

step 같은 경우 문제가 생길 수도 있다.(극한으로 생각하기)

홈페이지는 우리가 아는 naver.com 형식으로 되어있고 영어 소문자만 가능하다

뒤로가기, 앞으로가기, 주소 들어가기는 최대 5000번까지만 가능하다

1-3. 주어진 코드 형태

class BrowserHistory(object):

    def __init__(self, homepage):
        """
        :type homepage: str
        """
        

    def visit(self, url):
        """
        :type url: str
        :rtype: None
        """
        

    def back(self, steps):
        """
        :type steps: int
        :rtype: str
        """
        

    def forward(self, steps):
        """
        :type steps: int
        :rtype: str
        """

2. 접근 방법

접근 방법 같은 경우는 

2023.12.06 - [coding test] - Two Sum

Two Sum

이 글을 참고하면 된다

중요한 점은 이 문제는 순서가 중요한 선형 자료구조 라는 것.

2-1. 선형 자료구조 : list

리스트 자료구조에는 array 와 linked가 있다. 물론 array list 자료구조도 똑같은 시간 복잡도로 문제를 해결할 수 있지만, 이 문제는 리스트 중간에 새로운 요소를 끼워넣어야 하는 부분이 존재하기 때문에 linked list로 푸는것이 더 효율적일 것이다.

즉 이 문제는 링크드 리스트를 구현하는 그대로 문제를 풀어나가면 된다

2-2. 문제 해결 과정

class BrowserHistory(object):

    def __init__(self, homepage):
        # head 노드 만들기
        

    def visit(self, url):
        # visit은 새로운 노드를 추가하는 것
        # 마지막으로 추가된 노드는 tail이자 prev 노드
        # 새로운 url이 추가 됐을 때는 해당 노드 뒤 노드는 모두 삭제하고 해당 노드는 prev 노드가 된다
        

    def back(self, steps):
        # 반복문을 돌면서 step 수만큼 앞으로 간다
        # 해당 노드는 prev 노드가 된다

    def forward(self, steps):
		# 백과 같다

3. 해결 코드

# 노드 만드는 클래스 작성
class ListNode(object):
    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):
        # 제일 처음 들어가는 홈페이지 (head 노드 설정)
        # head와 current가 모두 첫번째 노드(홈페이지)를 가리키도록
        self.head = self.current = ListNode(val=homepage)

    def visit(self, url):
        # 새로운 visit 노드 생성(예시에서는 구글을 들어간다)
        # ListNode(val=url, prev=self.current) => visit 노드기 생성되면서 prev는 current로 지정되어있는 노드(현재는 첫번째 노드)를 가리켜야 한다
        # self.current.next_ => current에 해당하는 노드의 next는(현재는 첫번째 노드) 새로 생기는 visit 노드를 가리켜야한다
        # 현재 양방향으로 연결되어있다

        # 만약 새로운 노드를 추가한다면 이전 노드와 똑같이 연결되고 그 이후의 것은 GC에 의해서 사라진다
        self.current.next_ = ListNode(val=url, prev=self.current)

        # current는 새로 생성된 노드를 가리켜야 하기때문에 한칸 옮겨준다
        self.current = self.current.next_

        return None

    def back(self, steps):
        # step 수만큼 움직여야 하기 때문에 반복문을 사용한다
        # step 수가 0보다 크고,
        # current 노드(가장 최근노드)의 prev 가 None이 아니면(None이면 가장 첫번째 노드라는 것)
        while steps > 0 and self.current.prev != None:
            # step을 하나씩 뺀다
            steps -= 1
            # 현재 current 노드의 prev(바로 이전 노드)를 current 로 지정한다
            self.current = self.current.prev
        # step을 다 썻거나 가장 처음 노드라면 그 val 값을 리턴해준다
        return self.current.val
        

    def forward(self, steps):
        while steps > 0 and self.current.next_ != None:
            steps -= 1
            self.current = self.current.next_
        return self.current.val