23.03.18. 풀었던 문제들

Leetcode 1472. Design Browser History

 문제에서 주어진 대로 풀면 되는 문제. 간단한 구현 문제이다.

 입력은 5000이기 때문에 vector.erase() 등을 사용해 O($n^{2}$)으로 풀어도 2천만 정도로 상관 없다. 그러나 효율적으로 생각해 보면 erase는 O(n)의 시간이 걸리기 때문에 사용하지 않고 생각해 보자.

 전체 history를 한 vector에 넣고 [현재 탐색 가능한 길이]를 len으로 저장한다. 만약 idx가 len-1이라면 idx가 최신인 상태이고, idx가 len - 2 이하라면 back() method를 몇 번 호출해 forward를 할 수 있는 상태이다. 이 때 forward는 최대 len-1까지만 진행할 수 있다. 그러면

• back할 때는 len과 상관없이 back하면 된다.
• forward할 때는 len보다 더 나가지 않도록 idx 범위를 조정한다. - min(len - 1, steps + idx)
• visit할 때는 forward 기록이 모두 삭제되므로 idx + 1로 설정한다.

 이 세가지를 이용해 공간을 낭비하지 않고, erase() 없이 [현재 탐색가능한 범위]를 저장함으로써 효율적으로 구현했다. 또한 최대 입력 값인 5000을 미리 저장하지 않았기 때문에 메모리도 최적화되어 있다. 실제로 코드를 돌려보면 99% beat한다.

// Runtime 117 ms Beats 99.39%
// Memory 56.7 MB Beats 99.5%

class BrowserHistory {
public:
    int idx; // current index
    int len; // max history size
    vector<string> histories;
    BrowserHistory(string homepage) {
        histories.push_back(homepage);
        len = 1;
        idx = 0;
    }
    
    void visit(string url) {
        idx++;
        if(idx < (int)(histories.size())){
            histories[idx] = url;
            len = idx + 1;
        }
        else{
            len++;
            histories.push_back(url);
        }
    }
    
    string back(int steps) {
        // idx -= steps;
        // if(idx < 0) idx = 0;
        idx = max(0, idx - steps);
        return histories[idx];
    }
    
    string forward(int steps) {
        // idx += steps;
        // if(idx >= len) idx = len - 1;
        idx = min(len - 1, idx + steps);
        return histories[idx];
    }
};

 

시간복잡도

 visit(), back(), forward()에서 모두 O(1)이다. 따라서 operation이 n개 주어질 때 O(n).

 

공간복잡도

 worst case visit()이 n번 불러질 때 vector size가 n이 되므로 O(n)이다.

 

후기

 leetcode에도 구현 문제가 있구나. 정말 매일매일 풀면서 폼 유지하긴 좋은 것 같다. 이러고 코테기간 되면 지금까지 틀렸던 문제나 기출문제, 다음에 풀어볼 문제 풀면서 쫙 올리면 될 듯