[Java] leetcode 1472. Design Browser History

1. 알아야 할 개념

• 링크드리스트

문제

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

Design Browser History - LeetCode

웹사이트 뒤로가기 앞으로 가기 (undo, redo) 기능을 구현하는 문제

풀이

리스트의 삽입, 삭제가 많이 일어남으로 문자열을 저장할 자료구조로 링크드 리스트 사용하였다. 

풀이 알고리즘은 다음과 같다.

 

1. 문자열 담을 리스트, 현재 위치 인덱스를 저장할 변수를 초기화한다. 
2. visit 메서드를 구현한다.
   1. 하나 추가 됐으니깐 curPoint += 1  을 한다. 
   2. curPoint가 배열 끝 지점에 다다랐으면 add 메서드를 , 그게 아니라면 set 메서드를 사용하여 url 리스트를 update 한다. 
   3. visit을 하면 현재지점 curPoint 이후의 지점 정보는 삭제 하라그랬음으로 while문을 이용하여 ( 배열 사이즈 - curPoint + 1) 만큼 삭제를 한다. 
3. back 메서드를 구현한다. 
   1. 인덱스를 curPoint  - steps 값이 음수이면 0 을 그렇지 않으면 그대로 리턴한다.
4. forward 메서드를 구현한다. 
   1. curPoint + step 한것이 배열 마지막 인덱스위치 보다 크면 마지막 위치를 , 그렇지 않으면 curPoint + step 위치의 문자열을 리턴한다.

코드

class BrowserHistory {

    String homepage;
    LinkedList<String> history;
    int curPoint;

    public BrowserHistory(String homepage) {
        this.homepage = homepage;
        history = new LinkedList<>();
        history.add(homepage);
        curPoint = 0;
    }

    public void visit(String url) {
        curPoint++;
        if (curPoint == history.size()) {
            history.add(url);
        } else {
            history.set(curPoint, url);
        }

        while (curPoint < history.size() -1) {
            history.removeLast();
        }
    }

    public String back(int steps) {
        curPoint = curPoint - steps < 0 ? 0 : curPoint - steps;
        return history.get(curPoint);
    }

    public String forward(int steps) {
        curPoint = curPoint + steps > history.size() - 1 ? history.size() - 1 : curPoint + steps;
        return history.get(curPoint);
    }
}