폴더 목록이 있다고 가정하고 해당 폴더의 모든 하위 폴더를 제거하고 제거한 후 폴더를 순서에 관계없이 반환해야 합니다. 여기서 폴더[i]가 다른 폴더[j] 내에 있는 경우 해당 폴더의 하위 폴더로 표시됩니다. 경로는 folder1/subfolder2/... 등과 같습니다.
입력이 다음과 같다고 가정합니다.
["/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"], then the output will be: ["/myfolder","/another/final","/another/document"]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 경로의 길이에 따라 폴더 배열 정렬
- 하나의 맵 m 및 다른 배열 생성
- 범위 0에서 경로 배열 크기 - 1에 있는 i의 경우
- :=path_array[i]
- temp :=빈 문자열
- 플래그를 true로 설정
- 0부터 s까지의 범위에 있는 j의 경우
- temp :=temp + s[j]
- j를 1 증가
- j <배열의 크기이고 s[j]가 '/'가 아닌 동안
- temp :=temp + s[j], j를 1 증가
- m[temp]가 false가 아니면 flag :=false, 중단
- 플래그가 true이면 ans에 s를 삽입하고 m[s] :=true로 설정합니다.
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
static bool cmp(string s,string x){
return s.size()<x.size();
}
vector<string> removeSubfolders(vector<string>& f) {
sort(f.begin(),f.end(),cmp);
map <string,bool> m;
vector <string> ans;
for(int i =0;i<f.size();i++){
string s= f[i];
string temp="";
bool flag = true;
for(int j =0;j<s.size();){
temp+=s[j];
j++;
while(j<s.size() && s[j]!='/'){
temp+=s[j];
j++;
}
if(m[temp]){
flag = false;
break;
}
}
if(flag){
ans.push_back(s);
m[s]=true;
}
}
return ans;
}
};
main(){
vector<string> v = {"/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"};
Solution ob;
print_vector(ob.removeSubfolders(v));
} 입력
["/myfolder","/myfolder/secondfolder","/another/document","/another/document/extrafolder","/another/final"]
출력
[/myfolder, /another/final, /another/document, ]