🚥 문제 🚥
Top Interview 150 중
71. Simplify Path
🍿 난이도 : 리트코드 기준 Medium
🚧 알고리즘 : stack
🚦 풀이1 🚦
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
paths = path.split('/')
for dir in paths:
if (dir == ''):
if (stack and stack[-1] == '/'):
continue
else:
stack.append('/')
else:
if (dir == '.' or dir == '..'):
continue
if (stack and stack[-1] == '/'):
stack.append(dir)
if (len(stack) > 1 and stack[-1] == '/'):
stack.pop()
return "".join(stack)🚧 python의 stack을 위해 list 자료구조를 사용했다.
🏗 paths : 입력값 path가 "/"를 기준으로 나누어진 리스트
🚧 "/"를 기준으로 나누게 되면서, path의 기준이 되는 "/"값이 사라졌다.
세번째 예시인 "/home//foo/"입력값을 기준으로, paths에 들어가는 값은 ['', 'home', '', 'foo', '']이다.
그래서 ""로 들어간 값에 대해서 "/"라고 생각하고 진행했다. 중복 값을 제거해주기 위해 "/"가 stack의 top에 있고, 지금 디렉토리가 "/"일 경우에는 continue로 지나쳤다.
🚧 처음에는 문제를 읽을 때, ".", ".."은 각각 현재 디렉토리, 부모디렉토리를 가리키는 값이고, 이 값들에 대해서는 제외하고 파싱하라는 것으로 이해했다. 그래서,
if (dir == '.' or dir == '..'): continue 와 같이 ".", ".."에 대해서는 무시하도록 했다.
풀이 결과 : 실패
🥲 테스트케이스 "/a/./b/../../c/"에서 실패했다.
위의 테스트케이스를 통해서 ".", ".."에 대해서도 생각해줘야 한다는 것을 알게되었다.
이미 위치가 루트인 경우를 제외하고는 모두 적용해줘야 하는 문제였다.
테스트케이스에서 "/"에 대한 처리만 하고 난 이후의 path값은 "/a/b/../../c"가 된다.
풀어보면, a디렉토리 하위에 b디렉토리가 있고, 그 부모의 부모의 디렉토리에서 다시 c디렉토리로 이동해야한다.
그래서 b 디렉토리의 부모인 a, a의 부모인 root까지 가서, 다시 c디렉토리로 이동했기 때문에 이 테스트케이스의 답은 "/c"가 된다. 아래와 같은 폴더 구조를 가지고 있다고 생각하면 쉽다.
root
├ a/
├├ b/
├├ c/
🚦 풀이2 🚦
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
paths = path.split('/')
for dir in paths:
if (dir == ''):
if not stack:
stack.append(dir)
else:
if (dir == '.'):
continue
if (dir == ".."):
if (len(stack) > 1):
stack.pop()
continue
stack.append(dir)
if (len(stack) == 1):
return "/"
return "/".join(stack)🚧 join할 때 '/'를 기준으로 다시 넣어줄 수 있다는 것을 떠올리고, 이전에 풀때 리스트의 ''값을 스택에 '/'로 넣어주는 부분을 삭제했다.
첫 '/'를 제외하고는 '//'값이 있을 때만 ''값이 생긴다는 것을 알게 되어, '/'값은 처음빼고 모두 무시했다.
🚧 단독으로 stack에 들어있는 ''값은 '/'와 join될 때 결과가 ''로 나왔기 때문에, 마지막에 stack에 1개의 값만 있을 때는 '/'을 리턴해주었다.
🚧 이번에 작성할 때는 위의 테스트 케이스를 참고해서 만들었다.
사실 현재 디렉토리를 의미하는 '.'은 이 문제에서는 의미가 없기 때문에, continue를 이용해서 무시했다.
🚧 '..'은 stack에 값이 있을 경우 stack에 쌓인 원소를 하나 삭제했다.
앞의 디렉토리가 사라졌으므로, 부모디렉토리 단계로 올라간다는 의미다.
stack에 값이 없을 경우엔, 이미 root디렉토리에 있다는 의미이므로 continue를 통해 무시했다.
🚧 마지막으로 '.', '..', ''이 아닌 리스트의 원소들은 stack에 쌓아주었다.
풀이 결과
나쁘지 않은 결과였지만, 통과하고도 논리적으로 중복되는 것 같은 부분이 있다고 느꼈다.
🚦 풀이3 🚦
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
paths = path.split('/')
for dir in paths:
if (dir == '.' or dir == ''):
continue
if (dir == ".."):
if stack:
stack.pop()
continue
stack.append(dir)
return "/" + "/".join(stack)🚧 훨씬 훨씬 간결해졌다.
🚧 첫 번째 ''를 처리하는 부분과, 맨 마지막에 스택에 하나남은 ''를 처리하는 부분을 다듬었다. 리스트에 존재하는 모든 ''를 무시하고, 마지막에 join한 result string에 '/'를 맨 앞에 더해서 정답문자열을 만들었다.
🚧 이전풀이와 같이 '.'은 무시했고, '..'의 경우 stack에 있을 때만 pop하고 나머지의 경우 무시했다.
풀이 결과
이정도로 좋아질 거라고 기대하진 않았는데, '/'처리 부분만 수정했을 뿐인데 런타임 속도와 메모리부분에서 개선이 엄청 많이 되었다.
🥷 Solution Cheat
class Solution: def simplifyPath(self, path: str) -> str: return __import__('os').path.abspath(path)타인의 코드.
os.path.abspath()함수는 Python의 내장 모듈인 os 모듈에 있는 함수이고, 주어진 경로를 절대 경로로 변환해주는 기능을 제공한다.
주어진 path를 절대 경로로 변환한 후 그 결과를 반환하는 아주아주 짧고 충격적인 코드였다.
별거아닌데, 나도 os모듈을 알고 있었는데. 전혀 생각지도 못했다.
이런 코드를 망설임없이 내뱉을 수 있어야 파이썬 마스터라고 할 수 있는걸까?
