[Leetcode] 71. Simplify Path - JS

https://leetcode.com/problems/simplify-path/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- '/'로 시작하는 Unix 스타일 절대경로를 단순화된 표준경로로 변환하여 반환하라

Unix 스타일 규칙
- '.'는 현재 디렉터리
- '..'는 이전/상위 디렉터리
- '//', '///' 등 복수의 연속 슬래시는 '/' 단일 슬래시 처리
- 위 규칙과 일치하지 않는 일련의 마침표는 유효한 디렉터리 또는 파일 이름으로 처리된다.
    ex) '...', '....'는 유효한 디렉터리 또는 파일 이름으로 처리된다.

단순화된 표준 경로 규칙
- 경로는 단일 슬래시 '/'로 시작해야한다.
- 경로 내의 디렉터리는 정확히 1개의 '/' 슬래시로 구분되어야한다.
- 루트 디렉터리가 아닌 이상 슬래시 '/'로 끝나면 안된다.
- 현재 또는 상위 디렉터리를 나타내는 '.', '..'가 포함되면 안된다.


제한조건
--------------------
- 1 <= path.length <= 3000
- path는 영어 소문자, '.', '/', '_', 숫자로 구성된다.
- path는 유효한 unix 절대경로이다.

 

2. 접근 방법

접근방법
--------------------
stack 자료구조인 std 배열을 초기화한다.
기존 경로를 우선 '/' 기준으로 spilt 메서드로 구분해준다.
그러면 '/'으로 구분된 요소들로 구성된 배열이 생성되는데,
각 요소들의 값에 따라 조건에 따라 std 배열에 넣고 빼고해준다.

요소 값이 빈값이거나 '.' 한개인 경우 std에 넣어줄 필요가 없다.
요소 값이 '..'이면 상위폴더로 이동해야하니 std에 저장된 마지막 값을 제거한다.
그 외의 경우는 std에 마지막에 추가한다.

반복문이 종료되면 루트 경로를 나타내는 '/'에 std를 '/'로 합친 결과값을 반환한다.

 

 

3. 코드

var simplifyPath = function(path) {
    let dirs = path.split('/');
    let std = []; 
    for (let dir of dirs) {
        if (dir === '.' || dir === '') continue;
        if (dir === '..') {
            std.pop();
        } else {
            std.push(dir)
        }
    }
    return '/' + std.join('/');
};

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

'/'를 기준으로 구분해서 dir로 구성된 배열을 만든다.

dir 값이 빈칸이거나 '.'인 경우는 무시하고 '..'인 경우는 상위 디렉터리로 이동해야하므로 std에 저장된 최신의 값을 제거한다.

 

마지막으로 경로 맨 앞에 '/' 붙이고 std를 '/'로 붙이면 간단하게 풀 수 있다.