Today I Learned

오늘도 leetcode에서 코테 공부

Simplify Path

Leetcode 71번 https://leetcode.com/problems/simplify-path/description/

문제

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:
The path starts with a single slash '/'.
Any two directories are separated by a single slash '/'.
The path does not end with a trailing '/'.
The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')
Return the simplified canonical path.

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

풀이 과정

• 절대경로 문자열 path를 규칙에 맞게 단순화된 경로로 바꾸는 문제이다. 이 문제는 stack과 set을 이용해 해결했다.

1. ArrayDeque을 선언해 stack으로 활용한다. 이 스택에는 간소화된 각 경로의 디렉토리가 쌓인다.

2. 스킵할 디렉토리는 HashSet에 저장해둔다. "..", ".", ""이 스킵된다.

3. 주어진 조건에 맞게 조건문을 활용해 스택에 디렉터리를 쌓는다.

4. StringBuilder를 하나 만들어 간단 경로인 result를 만든다. 만약 result에 아무것도 없다면 '/'만, 그렇지 않다면 toString()을 이용해 String으로 반환하면 완료.

Java 코드

  public String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    Set<String> skip = new HashSet<>(Arrays.asList("..", ".", ""));

    for (String d : path.split("/")) {
      if (d.equals("..") && !stack.isEmpty()) {
        stack.pop();
      } else if (!skip.contains(d)) {
        stack.push(d);
      }
    }

    StringBuilder result = new StringBuilder();
    for (String d : stack) {
      result.insert(0, "/" + d);
    }

    return result.isEmpty() ? "/" : result.toString();
  }