Yunsu's Log

LeetCode 71: Simplify Path

6 min read

Note

/로 split한 뒤 스택으로 '.'·'..'를 처리하는 코드 구조를 설명합니다.

문제 링크

문제 요약

  • 입력: 유닉스 스타일 절대 경로 문자열 path (맨 앞은 '/')
  • 출력: 정규화된(canonical) 경로
  • 규칙: '.' 현재 디렉터리, '..' 상위 디렉터리, 연속 //는 / 하나, '...' 등은 유효한 이름

전체 코드

class Solution:
    def simplifyPath(self, path: str) -> str:
        dirs = path.split(sep='/')
 
        arr = []
 
        for name in dirs:
            if name == '..':
                if len(arr) > 0:
                    arr.pop()
            elif name == '.':
                continue
            elif name != '':
                arr.append(name)
 
        return '/' + '/'.join(arr)

코드 구조 설명

1. /로 분리

dirs = path.split(sep='/')
  • 경로를 '/' 기준으로 나누어 토큰 리스트로 만듦
  • 예: "/home//foo/" → ['', 'home', '', 'foo', '']
  • 연속 /는 빈 문자열 ''로 나타남

2. 스택 역할의 리스트

arr = []
  • 현재까지 유효한 경로를 디렉터리 이름 순서대로 쌓는 스택
  • '..'일 때는 여기서 한 칸 빼고, 일반 이름일 때는 여기에 넣음

3. 토큰별 처리

for name in dirs:
    if name == '..':
        if len(arr) > 0:
            arr.pop()
    elif name == '.':
        continue
    elif name != '':
        arr.append(name)
name의미동작
'..'상위 디렉터리스택에 뭔가 있으면 pop() (루트 위로는 안 감)
'.'현재 디렉터리아무 것도 하지 않음 (continue)
''연속 /에서 나온 빈 토큰name != ''에 걸리지 않아서 무시
그 외디렉터리/파일 이름arr.append(name)

'...'는 '.'·'..'가 아니고 빈 문자열도 아니므로 그대로 append 됩니다.

4. 정규화된 경로 반환

return '/' + '/'.join(arr)
  • 스택에 쌓인 이름들을 '/'로 이어 붙이고, 맨 앞에 '/' 하나 붙임
  • arr가 비어 있으면 "/" (루트) 반환

데이터 흐름 요약

단계역할
path.split(’/‘)슬래시 기준 토큰 분리
arr유효한 디렉터리 이름만 순서대로 유지 (스택)
’..’ → pop상위로 이동 (스택 비면 무시)
’.’ / ”무시
그 외 → append디렉터리 이름으로 추가
’/’ + ’/‘.join(arr)최종 경로 문자열

예시: path = “/home/user/Documents/../Pictures”

  • split → ['', 'home', 'user', 'Documents', '..', 'Pictures']
  • '' 무시, 'home' append → ['home']
  • 'user' append → ['home','user']
  • 'Documents' append → ['home','user','Documents']
  • '..' → pop → ['home','user']
  • 'Pictures' append → ['home','user','Pictures']
  • return "/home/user/Pictures"

시간·공간 복잡도

  • 시간: O(n) — path 한 번 순회, split·join 포함
  • 공간: O(n) — split 결과와 스택

심화 이론

Note

유닉스 스타일 절대 경로에서 '/'로 나눈 뒤 스택으로 '.'·'..'를 처리해 정규화된(canonical) 경로를 만드는 원리입니다.

유닉스 경로 규칙

  • /: 디렉터리 구분자. 연속된 //는 하나의 /로 취급.
  • .: 현재 디렉터리 → 경로에 영향을 주지 않음 (무시).
  • ..: 상위 디렉터리 → 한 단계 위로 올라감. 루트 위로는 올라갈 수 없음.
  • 그 외: ..., .... 등은 디렉터리/파일 이름으로 취급 (문자로만 보면 '.'·'..'가 아닌 것).

정규화된 경로 조건:

  • 맨 앞에 / 하나
  • 디렉터리 사이에는 / 하나
  • 맨 끝에 / 없음 (루트 "/" 제외)

핵심 아이디어: 스택으로 “현재까지의 경로” 유지

경로를 /로 split하면 토큰들이 나옵니다.

  • '': 연속 슬래시에서 나온 빈 문자열 → 무시
  • '.': 현재 디렉터리 → 경로에 영향을 주지 않음 (무시).
  • '..': 상위로 이동 → 스택이 비어 있지 않으면 pop (루트 위로는 안 감)
  • 그 외: 디렉터리/파일 이름 → 스택에 push

최종 결과는 스택에 쌓인 이름들을 /로 이어 붙이고, 앞에 '/'를 붙이면 됩니다.

알고리즘 흐름

  1. path.split('/') → 토큰 리스트 (빈 문자열, '.', '..', 일반 이름 혼합)
  2. 빈 리스트(스택) arr 준비
  3. 각 토큰에 대해:
    • '..' → 스택에 뭔가 있으면 pop()
    • '.' → 무시
    • '' → 무시
    • 그 외 → append(토큰)
  4. '/' + '/'.join(arr) 반환 (스택이 비면 "/")

예시

입력split 결과스택 동작결과
/home/['', 'home', '']['home']/home
/home//foo/['', 'home', '', 'foo', '']['home','foo']/home/foo
/home/user/Documents/../Pictures['', 'home', 'user', 'Documents', '..', 'Pictures']Documents에서 ..로 pop → ['home','user','Pictures']/home/user/Pictures
/../['', '..', '']루트 위로 못 가므로 pop 안 함/
/.../a/../b/c/../d/./['', '...', 'a', '..', 'b', 'c', '..', 'd', '.', '']... 는 이름 → ['...','b','d']/.../b/d

'.'과 '..'만 특별하고, '...'는 일반 이름으로 처리합니다.

요약

토큰의미동작
''연속 /무시
'.'현재 디렉터리무시
'..'상위 디렉터리스택이 비어 있지 않으면 pop
그 외디렉터리/파일 이름push

그래프 뷰