[Leetcode] 71. Simplify Path

문제 : https://leetcode.com/problems/simplify-path/description/

---

주어진 문자열 path는 Unix 스타일 파일 시스템에서 파일 또는 디렉토리까지의 절대 경로(슬래시('/')로 시작)입니다. 이를 간소화된 카노니컬 경로로 변환하세요.

Unix 스타일 파일 시스템에서 마침표(.)는 현재 디렉토리를 의미하며, 두 개의 마침표(..)는 상위 디렉토리를 의미합니다. 여러 개의 연속된 슬래시(//)는 하나의 슬래시(/)로 처리됩니다. 이 문제에서는 '...'와 같은 다른 마침표 형식은 파일, 디렉토리 이름으로 처리됩니다.

카노니컬 경로는 다음과 같은 형식을 가져야 합니다:

1. 경로는 슬래시(/)로 시작합니다.

2. 두 개의 디렉토리는 하나의 슬래시(/)로 구분됩니다.

3. 경로는 슬래시(/)로 끝나지 않습니다.

4. 경로에는 루트 디렉토리에서 대상 파일 또는 디렉토리까지의 디렉토리만 포함됩니다(즉, 마침표(.) 또는 두 개의 마침표(..)가 없음).

 

간소화된 카노니컬 경로를 구하세요.

---

스택을 사용합니다.

'/' 문자를 기준으로 토큰 분리를 한 다음 앞에서부터 탐색합니다.

탐색 중인 문자가 빈 값인 경우, 2번에 해당하는 경우이므로 무시합니다. (두 개의 슬래시)

마침표는 현재 디렉토리를 의미하므로 무시합니다.

두 개의 마침표(..) 는 상위 디렉토리를 의미하므로 스택의 탑에 있는 요소 하나를 제거합니다.

이 외의 문자열의 경우 스택에 추가합니다.

 

모든 문자열을 탐색했을 때, 스택을 탐색하면서 정답문자열의 뒤에서부터 스택의 위에 있는 문자열들을 추가해나갑니다.

정답 문자열을 추가할 때 앞에 슬래시를 추가합니다.

 

만약 정답 문자열이 빈 문자열의 경우 "/"가 정답이 됩니다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/71.%20Simplify%20Path.cpp