파일 시스템에서 하위 폴더 제거
- Barbara Streisand원래의
- 2024-10-31 04:35:01476검색
1233. 파일 시스템에서 하위 폴더 제거
난이도:중
주제: 배열, 문자열, 깊이 우선 검색, Trie
폴더 폴더 목록이 주어지면 해당 폴더의 하위 폴더를 모두 제거한 후 폴더를 반환합니다. 어떤 순서로든 답변을 보내실 수 있습니다.
폴더[i]가 다른 폴더[j] 내에 있으면 해당 폴더를 하위 폴더라고 합니다. 폴더[j]의 하위 폴더는 폴더[j]로 시작하고 그 뒤에 "/"가 와야 합니다. 예를 들어 "/a/b"는 "/a"의 하위 폴더이지만 "/b"는 "/a/b/c"의 하위 폴더가 아닙니다.
경로 형식은 '/' 다음에 하나 이상의 영어 소문자가 오는 형식의 하나 이상의 연결된 문자열입니다.
- 예를 들어 "/leetcode" 및 "/leetcode/problems"는 유효한 경로이지만 빈 문자열 및 "/"는 유효하지 않습니다.
예 1:
- 입력: 폴더 = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
- 출력: ["/a","/c/d","/c/f"]
- 설명: 폴더 "/a/b"는 "/a"의 하위 폴더이고 "/c/d/e"는 파일 시스템의 "/c/d" 폴더 안에 있습니다.
예 2:
- 입력: 폴더 = ["/a","/a/b/c","/a/b/d"]
- 출력: ["/a"]
- 설명: "/a/b/c" 및 "/a/b/d" 폴더는 "/a"의 하위 폴더이므로 제거됩니다.
예 3:
- 입력: 폴더 = ["/a/b/c","/a/b/ca","/a/b/d"]
- 출력: ["/a/b/c","/a/b/ca","/a/b/d"]
제약조건:
- 1 <= 폴더.길이 <= 4 * 104
- 2 <= 폴더[i].length <= 100
- 폴더[i]에는 소문자와 '/'만 포함됩니다.
- 폴더[i]는 항상 '/' 문자로 시작합니다.
- 각 폴더 이름은 고유합니다.
힌트:
- 폴더를 사전순으로 정렬하세요.
- 현재 요소를 배열에 삽입한 다음 하위 폴더를 모두 제거할 때까지 반복하고 요소가 더 이상 남지 않을 때까지 반복합니다.
해결책:
정렬과 문자열 비교를 조합하여 활용할 수 있습니다. 아래 단계에서는 PHP의 솔루션을 간략하게 설명합니다.
사전순으로 폴더 정렬: 사전순으로 폴더 경로를 정렬하면 모든 하위 폴더가 즉시 상위 폴더를 따르게 됩니다. 예를 들어 정렬된 목록에서 "/a" 다음에 "/a/b"가 표시되므로 하위 폴더 관계를 쉽게 확인할 수 있습니다.
하위 폴더 식별 및 필터링: 정렬된 목록을 반복하여 현재 폴더 경로가 이전에 추가된 경로의 하위 폴더인지 확인할 수 있습니다. 그렇다면 건너뜁니다. 그렇지 않은 경우 결과 목록에 추가합니다.
PHP에서 솔루션 구현: 결과 목록에 마지막으로 추가된 폴더 경로를 추적합니다. 현재 폴더가 이 마지막 폴더로 시작하고 바로 뒤에 /가 오면 하위 폴더이므로 무시해야 합니다.
이 솔루션을 PHP로 구현해 보겠습니다: 1233. 파일 시스템에서 하위 폴더 제거
설명:
정렬: sort() 함수는 폴더를 사전순으로 정렬합니다. 하위 폴더가 상위 폴더를 직접 따르기 때문에 하위 폴더 관계를 더 쉽게 찾을 수 있습니다.
각 폴더를 반복:
- 결과가 비어 있거나(첫 번째 반복) 현재 폴더 경로가 마지막으로 추가된 폴더와 / 뒤에 오는 폴더로 시작하지 않는 경우 하위 폴더가 아니며 결과 배열에 추가됩니다.
- 마지막 폴더 경로로 시작하고 바로 뒤에 /가 있으면 하위 폴더이므로 결과에 추가하는 것을 건너뜁니다.
결과: 이 함수는 하위 폴더를 제외하고 루트 폴더만 포함하는 결과를 반환합니다.
이 접근 방식은 정렬 단계로 인해 O(n log n)의 시간 복잡도로 효율적이며 선형 스캔은 O(n ) 문제의 제약 내에서 더 큰 입력을 처리하는 데 적합한 솔루션입니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
- 링크드인
- 깃허브
위 내용은 파일 시스템에서 하위 폴더 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!