유닉스 경로 단순화 (Simplify Path 원리)

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

---

관련 문제

• LeetCode 71: Simplify Path - 코드 구조 설명