폴더 경로 목록이 주어졌을 때, 다른 폴더에 포함된 모든 하위 폴더(sub-folder)를 제거하고 남은 폴더들을 임의의 순서로 반환하는 문제입니다. 여기서 folder[i]가 다른 folder[j] 내부에 위치한다면, folder[i]는 folder[j]의 하위 폴더로 간주됩니다. 경로는 /folder1/subfolder2/... 와 같은 형태로 표현됩니다.
문제 예시
입력이 다음과 같다고 가정해 보겠습니다.
["/myfolder", "/myfolder/secondfolder", "/another/document", "/another/document/extrafolder", "/another/final"]
이 경우 출력은 다음과 같습니다.
["/myfolder", "/another/final", "/another/document"]
/myfolder/secondfolder는 /myfolder의 하위 폴더이고, /another/document/extrafolder는 /another/document의 하위 폴더이므로 결과에서 제외됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 폴더 배열을 경로 길이 기준으로 오름차순 정렬합니다.
- 이미 등장한 폴더를 추적하기 위한 맵(map) m과 결과를 저장할 배열 ans를 생성합니다.
- 각 경로에 대해 슬래시(/)를 기준으로 상위 디렉터리부터 순차적으로 확인하며, 이미 맵에 존재하는 상위 폴더가 발견되면 해당 경로는 하위 폴더이므로 제외합니다.
- 하위 폴더가 아닌 경우에만 결과 배열에 추가하고, 맵에 해당 경로를 기록합니다.
알고리즘 상세 단계
- 경로 길이를 기준으로 폴더 배열을 정렬합니다.
- 맵 m과 배열 ans를 초기화합니다.
- i를 0부터 경로 배열 크기 - 1까지 반복합니다.
- s := path_array[i]
- temp := 빈 문자열
- flag := true로 설정
- j를 0부터 s의 크기까지 반복합니다.
- temp에 s[j]를 추가하고 j를 1 증가시킵니다.
- j가 배열 크기 미만이면서 s[j]가 '/'가 아닌 동안 temp에 문자를 계속 추가합니다.
- m[temp]가 true라면(상위 폴더가 이미 존재한다면) flag := false로 설정하고 반복을 종료합니다.
- flag가 true인 경우 s를 ans에 삽입하고 m[s] := true로 설정합니다.
- ans를 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#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]
코드 설명
이 알고리즘의 핵심은 정렬에 있습니다. 경로를 길이순으로 정렬하면 항상 부모 폴더가 자식 폴더보다 먼저 처리됩니다. 따라서 각 경로를 처리할 때, 슬래시를 기준으로 잘라낸 중간 경로(상위 디렉터리)가 이미 맵에 존재하는지만 확인하면 됩니다.
예를 들어 "/myfolder/secondfolder"를 처리할 때 먼저 "/myfolder"를 검사하게 되는데, 이 경로가 이미 맵에 등록되어 있다면 현재 경로는 하위 폴더임이 확실하므로 즉시 제외됩니다. 시간 복잡도는 정렬에 O(n log n), 각 경로 검사에 O(L)(L은 경로 길이)이 소요되어 전체적으로 효율적입니다.