leetcode medium : simplify path

Simplify Path - LeetCode

Simplify Path - LeetCode

 

유닉스 absolute path에는 .이나 .. 등 현재 폴더나 상위 폴더를 의미하는 심볼이 들어갈 수 있는데 이거 때문에 현재 폴더를 . 이렇게 표현해도 되지만 ./../folder 이런식으로 위로 갔다가 다시 내려올수도 있다. ././././. 이것도 현재 폴더가 될수있고.. 디렉토리 구분자를 /로 쓰는 사람도 있지만 //로 쓸수도 있기 때문에 이런 것들을 고려해서 path를 simplify하는게 문제의 요구사항이다.

 

처음엔 아주 naive하게 풀었다.

class Solution:
    def simplifyPath(self, path: str) -> str:
        result_path = []
        
        i = 0
        while i < len(path):
            while i < len(path) and path[i] == '/':
                i += 1
                
            if i == len(path):
                break
                
            j = i
            while j < len(path) and path[j] != '/':
                j += 1
                
            fname = path[i : j]
            
            i = j
            
            if fname == '.':
                continue
            elif fname == '..':
                if not result_path:
                    continue
                
                result_path.pop()
                continue
            
            result_path.append(fname)
        
        return "/" + "/".join(result_path)

 

현재 경로를 담은 result_path를 스택처럼 관리하며 ..가 나오면 pop하고 새 폴더가 나오면 스택에 추가하는 방식으로 한 거다.

결과 : 시간복잡도 효율성 5%의 submission 제침, 공간복잡도 효율성 82%의 submission 제침

 

즉 시간복잡도에서는 95%보다 못했다는 거고 공간복잡도에서는 상위 18%에 들었다는거다.

시간적으로 좀더 빠르게 할 방법이 없을까? 내 solution이 정말 optimal일까?

 

음 ㅋㅋ 가장 바깥쪽 while i < len(path):을 while True로 바꿔줬더니 (어차피 내부에 반복문 종료조건이 있어서) 67%를 beat했다고 나왔다. 알고리즘적으로는 더 optimize할게 없는거같다. 굳

 

 

 

방금 다른 사람 솔루션을 보고왔다

    def simplifyPath(self, path):
        stack = []
        for p in path.split("/"):
            if p == "..":
                if stack:
                    stack.pop()
            elif p and p != '.':
                stack.append(p)
        return '/' + '/'.join(stack)

ㅋㅋ 자살해야겠다 ..ㅎㅎ