23.04.12. 풀었던 문제들

Leetcode 71. Simplify Path

 이번 주는 stack 관련된 문제가 나오는 주인가보다. 계속 stack 문제가 나온다.

 일단 문제 조건은

• directory 구분은 /로 한다. //와 같이, / 사이가 빈 경우에는 아무것도 하지 않는다.
• .은 아무것도 하지 않는다
• ..은 상위의 directory를 가리킨다.

 

 그러면 /를 delimiter로 사용해 parsing한 뒤, "."이나 ""가 나오면 아무것도 하지 않고 ".."가 나왔을 때만 stack에서 pop하면 될 것이다. 그리고 그 결과를 계산하면 될 것. 사실상 string parsing문제임을 알 수 있다. 기억하자. string parseing은 stringstream, buffer, delimiter, while(getline) 4개를 이용해 구할 수 있다.

// Runtime 8 ms Beats 46.38%
// Memory 9.3 MB Beats 70.22%

class Solution {
public:
    string simplifyPath(string path) {
        // parse by '/'
        vector<string> directories;
        istringstream iss(path);
        string buffer;
        while(getline(iss, buffer, '/')) directories.push_back(buffer);
        
        // use stack. pop and push.
        vector<string> canonical;
        for(string directory : directories){
            if(directory == "" || directory == ".") continue;
            else if(directory == ".."){
                if(!canonical.empty()) canonical.pop_back();
            }
            else canonical.push_back(directory);
        }

        string answer = "/";
        for(int i = 0; i<canonical.size(); i++){
            answer += canonical[i] + (i == canonical.size()-1 ? "" : "/");
        }
        return answer;
    }
};

 

시간복잡도

 string parsing에 path를 1번 순회, directories를 1번 순회, canonical을 1번 순회하므로 O(n)이다.

 

공간복잡도

 path size를 n이라고 했을 때, string vector directories, canonical, answer를 사용하는데 worst case O(n)의 크기를 가진다. 따라서 O(n).