[leetcode 71] Simplify Path

모든 경로를 canonical path로 바꾸는 문제

 

cf) canonical path란? 절대 경로는 절대 경로 인데 표준화된 절대 경로..?

무조건 경로 시작은 /로 시작하며 마지막엔 /가 붙지 않고 디렉토리 사이엔 하나의 /만 존재한다.

.이나 ..도 모두 계산해서 꼭 필요한 경로만 남기는 것이다.

 

예를 보자.

Example 1:

Input: "/home/" Output: "/home"

마지막이 "/"로 끝나서 /를 없애주었다.

 

Example 2:

Input: "/../" Output: "/"

Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

..을 하면 상위 경로로 이동된다. 따라서 /만 남음.

 

Example 3:

Input: "/home//foo/" Output: "/home/foo"

//를 /로 바꾼다.

 

Example 4:

Input: "/a/./b/../../c/" Output: "/c"

/a/. => /a와 같다.

/a/b/../../ => 가장 상위인 /로 간다.

따라서 /c만 남는다.

 

Example 5:

Input: "/a/../../b/../c//.//"  Output: "/c"

/a/../../ 상위 경로로 이동. 더이상 이동할 곳이 없으므로 /에서 멈춘다.

/b/../ 여전히 상위 경로 /에서 멈춤

/c//.// = /c와 동일

 

Example 6:

Input: "/a//b////c/d//././/.." Output: "/a/b/c"

같은 원리로 설명된다.

 

처음에 canonical path가 뭔지 도통 이해가 안가서 geeksforgeeks 보고 이해를 했다...

 

문제 풀이:늘 그렇듯이 문자열을 이용한 stack 문제이다.조건이 다양해서 까다로웠다. 3번째에 맞음 ㅠ 이런 문제 풀때마다 예외를 놓쳐서 틀린다. 예외 주의! 특히 마지막 dir를 처리하는 것이 중요하다. 자꾸 빼먹어서 에러..

 

처음에 stack에 push했다가 stack은 iterator가 없다는 것을 깨닫고 vector로 바꿈...stack, queue는 iterator가 없다!

 

1. 문자열을 받는다.

2. 문자열이 /이 아닌 경우 -> string dir에 append

3. 문자열이 /인 경우

3-1. dir가 .이다 => pass

3-2. dir가 ..이다 => if stack.size()>0 then pop; else 최상위경로이므로 pass

3-3. dir가 유효한 경로(1,2가 아님) => stack에 push중요한 점 3의 모든 경우에서 dir를 초기화해줘야 한다.

 

using namespace std;
class Solution {
public:
    string simplifyPath(string path) {
        
        vector<string> s;
        string dir;
        for(int i=1; i<path.size(); i++){
            if(path[i] !='/'){
                dir += path[i];
            }else {
                //check dir
                if(dir == ".."){
                    if(s.size()>0){
                        s.pop_back();
                    }
                    dir= "";
                }
                else if(dir == "."){
                    dir="";
                }else if(dir.length()>0){
                    s.push_back(dir);
                    dir = ""; //init dir
                }
            }
        }
        
        //if dir remains
        if(dir.length()>0){
            if(dir == ".." && s.size()>0){
                s.pop_back();
            }else if(dir !="." && dir!=".."){
                s.push_back(dir);
            }
        }
        
        string answer;
        if(s.size() == 0){
            answer += "/";
        }
        
        for(int i=0; i<s.size(); i++){
            answer += "/" + s[i];
        }
        return answer;
    }
};

 

 

또 다른 풀이

stringstream과 getline을 사용한 더 빠른 풀이이다.

 

stringstream이란?

cin처럼 입력을 받는 함수인데 getline에서 첫 번째 인자로 cin을 받아서 쓴 거 같다.

 

std::getline(string)getline은 두가지 종류가 있는데 자주 쓰는 건 이것

istream& getline(istream& is, string& str, char del);

• is: 입력 스트림 object ex) cin, stringstream
• str: 입력받은 문자열을 저장하는 string 객체
• del: 이 문자에 도달하면 문자열 추출이 중단된다.

class Solution {
public:
    string simplifyPath(string path) {
        stringstream ss(path);
        string line;
        vector<string> s;
        
        // '/'가 나올때마다 if문이 실행된다.
        while (getline(ss, line, '/')) {
            if (line.empty()) {
                continue;
            } //저장된 문자열이 없으면 넘어간다.
            
            //저장된 문자열이 ..라면
            if (line == "..") {
                if (!s.empty()) {
                    s.pop_back();
                }
            } else if (line != ".") {
                s.push_back(line);
            }//저장된 문자열이 ..과 .이 아니라면 s에 저장
        }
        string ans;
        for (const string &t : s) {
            ans.push_back('/');
            ans.insert(ans.end(), t.begin(), t.end());
        }
        return ans.empty() ? "/" : ans;
    }
};