[python3] 71. Simplify Path

풀이 일자: 23.04.12

난이도: [Medium]

분류: [String, Stack]

문제 내용

절대경로를 간단한 캐노니컬 경로로 바꿔서 리턴하는 문제였다.

 

 

문제 해결 흐름

 

1. 가장 먼저 떠오른 방법은 path의 글자를 하나씩 읽어가면서 stack에 넣고 ..와 .에 따라 처리해주는 방법이었다.

=> 결과는 여러 경우의 수를 따져가면서 처리를 하나씩 해줬는데 실패였다. 이런 예외사항을 고려하면 다른 게 또 걸리고 그런 식이었다. 다른 방식을 생각해보자.

 

예외의 경우  /./..stack      /hi///.././..

class Solution:
    def simplifyPath(self, path: str) -> str:
        ans = ['/'];

        dotCnt = 0;

        for s in path:
            if s == '/':
                if ans[-1] == '/':
                    pass
                elif ans[-1] == '.':
                    if dotCnt == 1:
                        ans.pop();
                    elif dotCnt == 2:
                        del ans[-3:]
                        while(len(ans) > 1 and ans[-1] != '/'):
                            ans.pop();
                    else:
                        ans.append(s)
                    dotCnt = 0;
                else:
                    ans.append(s);
            elif s == '.':
                dotCnt += 1;
                ans.append(s);
            else:
                ans.append(s);

            if len(ans) == 0:
                ans = ['/']
            print(ans)

        if ans[-1] == '.':
            if dotCnt == 1:
                ans.pop();
            elif dotCnt == 2:
                del ans[-3:]
                while(len(ans) > 1 and ans[-1] != '/'):
                    ans.pop();
        
        if len(ans) > 1 and ans[-1] == '/':
            ans.pop(-1);
        elif len(ans) == 0:
            return '/'


        return ''.join(ans);

 

2. 각 경우마다 처리를 달리 해주는 건 너무 비효율적인 방식인 것 같다. 

=> 이번에는 directory와 파일명에만 집중을 하자. /는 마지막에 사이사이에 넣어주면 되는거니까 /를 기준으로 split을 하고 단어단위로 끊어서 경로를 재설정해보자.

 

class Solution:
    def simplifyPath(self, path: str) -> str:
        dirFile = path.split('/');
        tmp = list();
        
        for i in range(len(dirFile)):
            if dirFile[i] == '.':   #.인 경우 단순히 현재 디렉토리를 의미하므로 무시
                pass;
            elif dirFile[i] == '..':  # ..인 경우 상위 디렉토리를 의미하므로 tmp내에 있는 상위경로 하나 삭제
                if len(tmp) >= 1:
                    tmp.pop();
            elif dirFile[i] != '':    # 경로명인 경우 그대로 tmp에 넣는다.
                tmp.append(dirFile[i]);
        
        if len(tmp) == 0:
            return '/';
        else:
            return '/' + '/'.join(tmp);

Time Complexity:  O(N)

시간복잡도는 path='/////////'이런식으로 나오는 경우 dirFile에는 ['','','','', ... ,''] 이런식으로 저장되게 될 것이고 이에 for문을 최대 path의 길이만큼의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N)

공간복잡도도 시간복잡도와 같은 이유로 최대 path의 길이만큼의 공간복잡도를 가질 것이다.

 

 

다른 해결 방식

1. 내 코드를 더 간결하게 만든 풀이가 존재했다.

class Solution:
    def simplifyPath(self, path):
        dirOrFiles = []
        path = path.split("/")
        for elem in path:
            if dirOrFiles and elem == "..":
                dirOrFiles.pop()
            elif elem not in [".", "", ".."]:
                dirOrFiles.append(elem)
                
        return "/" + "/".join(dirOrFiles)

 

Time Complexity:  O(N)

시간복잡도는 path='/////////'이런식으로 나오는 경우 dirFile에는 ['','','','', ... ,''] 이런식으로 저장되게 될 것이고 이에 for문을 최대 path의 길이만큼의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N)

공간복잡도도 시간복잡도와 같은 이유로 최대 path의 길이만큼의 공간복잡도를 가질 것이다.

 

 

문제 링크

https://leetcode.com/problems/simplify-path/description/

Simplify Path - LeetCode