71. Simplify Path

난이도: 중간 (Medium)

링크: LeetCode 71

풀이 날짜: 2025/10/22

 

1. 문제 이해

입력:

path = "/a/./b/../../c/"

출력:

"/c"

설명:

• UNIX 스타일 경로를 단순화하는 문제
• . → 현재 디렉토리, .. → 상위 디렉토리, 연속 /는 하나로 합침
• 최종적으로 최소한의 경로를 반환

 

2. 접근 방식 — Stack 활용

경로(path)를 / 기준으로 나눈 후(path = "/a/./b/../../c/" -> ['a', '.', 'b','..','..','c']) Stack을 이용해 유효한 디렉토리 또는 파일을 스택에 넣어서 관리하는 방식으로 풀이한다.

 

규칙:

1. '' 또는 . → 무시
2. .. → Stack에서 상위 디렉토리를 제거(pop)
3. 그 외 → Stack에 push. 유효한 디렉토리 또는 파일 경우.

마지막에 Stack에 남은 요소들을 '/'로 연결하고 가장 앞(root)에 '/' 를 붙여서 반환한다.

 

3. 풀이 코드

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  const pathArr = path.split('/');
  const stack = [];

  for(const p of pathArr) {
    // 더블 슬래시를 split 하는 경우 빈문자열이 생기기 때문에 이 경우도 건너뛴다.
    if(p === '' || p ==='.') { 
      continue;
    } else if(p === '..') {
      stack.pop(); // 상위 디렉토리 제거
    } else {
      stack.push(p)
    }
  }

  return '/' + stack.join('/') // root 에 슬래시 추가해줘야 함.
};

 

예시 시나리오

path = "/a/./b/../../c/", 최종 결과 = “/c”

단계	처리	Stack 상태
“/a”	push “a”	[“a”]
“.”	무시	[“a”]
“/b”	push “b”	[“a”,“b”]
“..”	pop	[“a”]
“..”	pop	[]
“/c”	push “c”	[“c”]

 

시간 복잡도 - O(N) — path 길이만큼 순회

공간 복잡도 - O(N) — Stack 사용

 

4. 핵심 개념 및 마무리

구분	설명
문제 유형	Stack, String Manipulation
핵심 아이디어	경로를 나눠 Stack으로 처리, .. → pop, . → 무시
시간 복잡도	O(N) — path 길이만큼 순회
공간 복잡도	O(N) — Stack 사용
포인트	Stack 구조를 이용해 상위 디렉토리 이동 처리

이 방식은 Stack만으로 상위 디렉토리 처리와 현재 디렉토리 무시를 직관적으로 구현할 수 있어, 효율적이고 간단하다.