LeetCode 71(Simplify Path, Python)

1. 문제 링크

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

Simplify Path - LeetCode

2. 문제 설명

• '/'로 시작하는 절대경로 (absolute path) path라는 문자열이 주어졌을 때, 이를 canonical path로 변환하여 반환
  • Unix-style file system에서 '.'는 현재 경로를 의미하고, '..'는 현재의 상위 경로를 의미하고, //는 /와 동일하게 여겨진다.
  • 이 문제에서 '...'와 같은, 위를 제외한 포멧은 파일/경로명을 의미 
• canonical path는 아래의 format을 따른다.
  • path가 '/'로 시작할 것
  • 두개의 경로는 '/'로 분리된다.
  • path는 '/'로 끝나지 않는다.
  • path는 root 경로에서 target 경로까지의 path 경로만을 포함한다. 
• 예시1) path = "/home/" → output = "/home"
  • path가 /로 끝나지 않아야 하므로, 마지막 /는 지워져야 함
• 예시2) path = "/.."/ → output = "/"
  • 루트 디렉토리는 최상위 디렉토리로, 더 이상 위로 올라갈 수 없음
• 예시3) path = "/home//foo/" → output = "/home/foo"
  • //는 /와 동일하게 여겨지며 canonical path는 /로 분리가 되므로, /로 변경
• 이렇게 까지 봐도 정확히 어떤 규칙인건지가 헷갈렸고, 결국 discussion에서 좀 더 문제를 잘 이해시켜주는 글을 발견했다.
  • 결국 '.'이면 continue, '..'는 이전 directory를 지우는 것, 그리고 //는 /로 replace하는 게 규칙으로 이해했다.
    • 여기서 아래 이미지의 5번은 누군가 reply를 달아주긴 했는데, output이 /home/usr/local/bin이 되는게 맞다.

 

3. 처음 풀이 

• '..'를 마주쳤을 때, 그 직전 directory를 제외하는 것을 어떻게 해야 깔끔하게 짤 수 있을까 하다가, 
• gpt에게 힌트를 구했는데.. 답을 알려주었다... (그래도 stack 자체로 다룬 문제는 오늘이 처음이라 답을 못찾았으면 좀 헤맬 뻔했다.)
• stack이라는 자료구조에 대해서는 바로 아래에서 부연 설명할 예정
• 우선 코드를 설명하면,
  • '//'는 바로 '/'로 replace를 시키고, path를 '/'를 기준으로 split시킨 리스트를 path_list로 저장해두었다.
  • 그리고 for문을 돌리면서, token이 ''이거나 '.'이면 stack에 쌓지 않고 continue를 하고, 
  • 만약 token이 '..'인데 stack에 값이 있으면 stack.pop을 해서 before directory를 제거하고, 
  • 그 이외의 케이스는 stack에 token을 append하는 구조로 작성되었다. 
  • 그릐고 마지막으로 '/'를 기준으로 join하여 output을 반환

class Solution:
    def simplifyPath(self, path: str) -> str:
        path = path.replace('//', '/')

        path_list = path.split('/')

        stack = []
        for token in path_list:
            if token == '' or token == '.':
                continue
            elif token == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(token)

        output = '/' + '/'.join(stack)

        return output

 

4. stack 자료구조에 대한 설명

• stack은 데이터를 저장하는 데 사용되는 선형 자료구조로, 데이터를 차곡차곡 쌓을 수 있는 구조. 
• 데이터를 쌓는 동작과 꺼내는 동작을 제공하며 후입선출(LIFO, Last In First Out) 방식을 따름
  • 반대로 queue의 경우 FIFO(First In First Out) 방식 
• stack은 주로 두가지 연산을 지원
  • push: 스택에 데이터를 추가하는 작업. 데이터는 스택의 맨 위에 추가됨
  • pop: 스택에서 데이터를 꺼내는 작업으로, 스택의 맨 위에 있는 데이터가 제거되고 반환 
• 일상에서 비유하면, 책을 쌓거나 접시를 쌓는 것과 유사한 개념. 가장 최근에 쌓은 책이나 접시가 가장 먼저 꺼내지게 됨
• 파이썬에서는 stack 자료형을 별도로 제공하진 않지만, 리스트가 사실 stack의 모든 연산을 지원
  • 결국 append()로 push연산을 하고, pop()으로 pop연산을 수행할 수 있음.
  • 함수 호출의 재귀적 동작, 브라우저의 뒤로가기 버튼과 같은 여러 상황에서 적용가능
• 여기에서도 '..'를 마주치면, 그 이전에 쌓았던 것들 중 가장 마지막 것을 꺼내는 pop연산이 적용이 되고 있음

5. 배운 점

• canonical path, stack