Simplify Path - LeetCode

Problem

1. input: absolute path 를 나타내는 문자열 path
2. output: path를 canonical path로 바꾸어 리턴
   • 1 <= path.length <= 3000
   • path consists of English letters, digits, period '.', slash '/' or '_'.
   • path is a valid absolute Unix path.

Idea

absolute path와 canonical path의 주된 차이는 ‘..’(상위 경로로 이동)이다.

즉 absolute path를 스택에 하나씩 저장 후, ‘..’에 대하여 pop을 해주면 canonical path로 변환할 수 있다 → Sol1

Solution

1. 스택

   ‘일반 경로 ‘→ 스택에 push

   ‘..’ → 스택 pop

   ‘.’, ‘/’, ‘’ → 무시

   import java.util.*
   
   class Solution {
       fun simplifyPath(path: String): String {
           val canonical = Stack<String>()
           loop@for (path in path.split("/")) {
               when {
                   path in listOf(".", "/", "") -> continue@loop
                   path == ".." -> if (!canonical.empty()) canonical.pop()
                   else -> canonical.push(path)
               }
           }
           return "/" + canonical.joinToString("/")
       }
   }
   

   시간 복잡도: 문자열 순회 = n

   

Point