[코테연습] 1233. Remove Sub-Folders from the Filesystem

- 배열 / 트라이 / DFS / 문자열 문제

 

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/description/?envType=daily-question&envId=2024-10-25

 

- 문제분석

 

• 주어진 folders 리스트에는 여러 파일 경로가 포함되어 있습니다.
• 예를 들어, ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]와 같은 경로가 주어질 수 있습니다.
• "/a/b"는 "/a"의 하위 폴더이므로, 최종 출력에서는 하위 폴더인 "/a/b"를 제거하고 "/a"만 남겨야 합니다.
• 최종 결과에는 중복되지 않는 최상위 폴더들만 포함되어야 합니다.

 

- 문제풀이

 

1. 사전적으로 정렬:

• 폴더 경로들을 사전순으로 정렬하여, 상위 경로와 그 하위 경로가 연속적으로 나타나도록 합니다.

2. 하위 폴더 확인 로직:

• 각 경로를 탐색하면서, 현재 경로가 이전 폴더의 하위 폴더인지 확인합니다.
• 하위 폴더인 경우 해당 경로를 무시하고, 그렇지 않으면 최상위 폴더로 추가합니다.

 

예시 설명

예를 들어, ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"]가 입력으로 주어졌을 때:

1. 정렬:
   • 경로들을 사전적으로 정렬하면: ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"].
2. 탐색 및 결과 생성:
   • "/a"는 결과에 추가됩니다.
   • "/a/b"는 "/a"의 하위 폴더이므로 무시됩니다.
   • "/c/d"는 결과에 추가됩니다.
   • "/c/d/e"는 "/c/d"의 하위 폴더이므로 무시됩니다.
   • "/c/f"는 결과에 추가됩니다.
3. 최종 결과:
   • 결과는 ["/a", "/c/d", "/c/f"].

> java

 

class Solution {
    public List<String> removeSubfolders(String[] folder) {
         // 사전적으로 정렬
        Arrays.sort(folder);
        
        List<String> result = new ArrayList<>();
        String prevFolder = "";

        for (String currFolder : folder) {
            // 현재 폴더가 이전 폴더의 하위 폴더인지 확인
            if (prevFolder.isEmpty() || !currFolder.startsWith(prevFolder + "/")) {
                result.add(currFolder);
                prevFolder = currFolder;
            }
        }

        return result;
    }
}

 

> java :: stream

 

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        // 사전적으로 정렬
        List<String> sortedFolders = Arrays.stream(folder)
                .sorted()
                .collect(Collectors.toList());
        
        List<String> result = new ArrayList<>();
        
        // Stream을 사용해 각 폴더를 처리
        sortedFolders.stream().reduce("", (prevFolder, currFolder) -> {
            // 현재 폴더가 이전 폴더의 하위 폴더가 아닌 경우 결과에 추가
            if (prevFolder.isEmpty() || !currFolder.startsWith(prevFolder + "/")) {
                result.add(currFolder);
                return currFolder; // 다음 비교를 위해 prevFolder 갱신
            }
            return prevFolder; // 이전 폴더 유지
        });
        
        return result;
    }
}

 

 

> python

 

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()

        result = []
        prev_folder = ''

        for current_folder in folder :
            if prev_folder == '' or not current_folder.startswith(prev_folder+'/') :
                result.append(current_folder)
                prev_folder = current_folder
        return result