문제 이해 단계
https://www.acmicpc.net/problem/22861
main 폴더 안에 있는 폴더의 총 개수 N과 파일의 총 개수 M이 주어진다.
그리고 폴더를 옮기는 횟수 K가 주어진다.
폴더를 옮긴다는 것은 폴더 A에 있던 하위 폴더와
파일들을 모두 폴더 B로 옮긴다는 것
그리고 마지막에 쿼리 Q가 주어지고,
그 쿼리에 맞는 파일의 종류가 몇 개인지,
그리고 파일의 수가 몇 개인지 출력하는 문제
사실문제가 상당히 길기 때문에, 링크를 타고 들어가서 문제를 읽고 오는 편이 낫다.
문제 접근 단계
입력으로 들어오는 것이 많다.
그렇기 때문에 더더욱 제한사항부터 살펴봐야 한다.
폴더(N)와 파일(M)의 개수는 최대 1,000개까지 가능하다.
파일을 옮기는 횟수(K)도 최대 1,000회까지 가능하다.
그리고 쿼리문(Q)도 1,000까지 가능하다.
이 점을 유의하면서 문제풀이에 들어간다.
상위/하위 폴더와 파일 구조를 나타내기
우선 이 문제부터 해결해야 한다.
main
├─ FolderA
│ ├─ File1
│ └─ File2
└─ FolderB
├─ FolderC
│ ├─ File4
│ └─ File5
├─ File1
└─ File3일단 이 그림을 보면 트리 구조랑 닮아있다.
다른 점은 각 노드가 문자열로 이루어져 있는 것뿐,
그래서 나는 map을 사용하여 key-value 방식을 사용하기로 했다.
key에는 상위폴더의 이름이 들어가고, value에는 하위폴더와 파일들이 들어간다.
map을 사용할 수 있는 이유는 문제에서
"main 폴더의 하위 디렉터리에 같은 이름의 폴더가 두 개 이상 존재할 수 없다."
라고 했기 때문이다.
key값으로는 무조건 폴더가 들어가는데, 이는 유일한 값이기에 가능해지는 것이다.
여기서 2가지를 더 생각해야 한다.
첫 번째는, 폴더와 파일을 구분하는 방식이 정수가 1/0에 차이이다.
그래서 pair을 사용하여 두 쌍으로 이름과 정수를 받아
해당 이름으로 된 엔티티(entity)가 폴더인지 파일인지 구분할 수 있도록 한다.
또한, 같은 폴더 내에는 동일한 이름의 파일이 존재하면 안 된다.
입력 단계에서는 크게 문제가 되지 않지만, 나중에 두 폴더를 합칠 때 문제가 생길 수 있다.
예를 들어, 폴더 A와 폴더 B에 file1이 동시에 존재하는데
폴더 A와 폴더 B를 합친다면 file1이 2개가 생겨버린다.
이를 방지하고자, value를 담는 컨테이너(하위 공간)를 set으로 선언해 줬다.
set으로 선언해 주면 중복을 허용하지 않기 때문에
자동적으로 같은 이름의 파일은 하나밖에 남지 않게 된다.
최종적으로 선언해 준 컨테이너는 다음과 같다.
map<string,set<pair<string,int>>> m;
폴더 A를 폴더 B로 옮기기
map을 사용하여 구조를 구성하였기 때문에 이건 쉽다.
그냥 map [폴더 A 이름]로 해당 set컨테이너에 있는 모든 것을
map [폴더 B 이름]의 set컨테이너에 추가하면 끝난다.
set으로 선언해 줬기 때문에 넣어주기만 해도 중복은 알아서 삭제된다.
쿼리문 출력하기
이 문제에서 핵심이 되는 부분이다.
출력을 해야 하는 것은 (파일의 종류, 파일의 개수)이다.
map으로 구조를 만들었기 때문에 폴더의 이름만 가지고도
해당 폴더 하위에 있는 폴더와 파일들을 모두 알 수 있다.
파일의 개수는 그냥 카운트하면 되지만, 문제는 폴더이다.
이 폴더 안에 또 파일과 폴더가 들어있어서 열어봐야 한다.
그리고 그 폴더 안엔 또 파일과 폴더가 들어있을 것이다.
여기서 '아 이건 재귀함수로 짜면 될 것 같은데?'라는 느낌이 들었다.
그런데 또 이런 생각이 들었다.
만약 폴더가 1000개가 있는데,
이게 마트료시카처럼 폴더 안에 폴더, 폴더 안에 폴더, 이런 식으로 1000개가 들어있다.
이럴 때 Q가 1,000이고 전부 입력이 main이 들어온다면?
재귀함수 1000번 * 1000을 해야 한다.
딱 봐도 시간초과가 날 것 같아서 한번 계산했던 값은 저장해 두는 방법이 필요할 것 같다.
즉, 메모라이징 기법을 사용하기로 했다.
DP를 사용한다는 것과 비슷하다.
계산했던 값 저장하기
일단 게산했던 값을 저장할 공간이 필요한데, 폴더 이름이 모두 문자열이다.
때문에 해당 인덱스 배열도 map을 사용하여 key-value를 사용하여 저장한다.
저장해야 할 것은 (종류, 개수)이므로 pair을 사용한다.
dp를 돌리는 방식은 간단하다. 쿼리로 들어온 폴더 내부의 요소를 하나씩 검사한다.
이때 set 컨테이너를 하나 만든다. 이는 종류를 카운트하기 위해 만들어 둔 것이다.
요소가 파일이라면 개수+1을 하고 set에 요소를 추가한다.
요소가 폴더라면 해당 요소를 이름으로 하는 dp를 다시 호출한다.
반환하는 것은 (set, 개수) 쌍이다.
이렇게 반환받은 쌍을 dp배열에 저장해 둬 메모라이징 해둔다.
DP 쪽은 코드를 보면서 하는 것이 더 더 편할 것이다.
문제 구현 단계에서 더 자세히 설명하겠다.
문제 구현 단계
map<string,set<pair<string,int>>> m;
map<string,pair<set<string>,int>> d;
// N+M만큼 반복
for(int i = 0; i < N+M; i++){
string a,b;
int offset; // 폴더인지 파일인지
cin >> a >> b >> offset;
m[a].insert({b,offset}); // 상위폴더 set 컨테이너의 추가
d[a].second = 0; // a 이름을 가지는 key 생성
}우선 입력받는 부분이다.
맨 위에는 폴더와 파일을 구성하는 map과 dp배열을 구성하는 d이다.
입력으로는 N+M횟수만큼 a를 key로 가지는 폴더를 생성하여 그 안에 넣는 것이다.
또한 dp배열에도 a를 key로 가지는 map을 생성하도록 한다.
void merge(string from, string to){
for(auto it : m[from]) m[to].insert(it);
// from 키를 삭제
m.erase(from);
}
cin >> K;
for(int i = 0; i < K; i++){
string a,b;
cin >> a >> b;
stringstream ss1(a);
stringstream ss2(b);
string from,to;
while(getline(ss1,from,'/')); // 마지막 위치
while(getline(ss2,to,'/')); // 마지막 위치
merge(from,to);
}K 횟수만큼 a폴더에 있는 요소들을 b폴더로 옮기는 것이다.
여기서 stringstream일 사용한 이유는
입력으로 들어오는 것이 모두 main/folder/...
이런 식으로 ' / '를 구분자로 사용하여 끊어져있기 때문이다.
' / '를 구분자로 하여 문자열을 나누고
while문으로 가장 마지막에 있는 문자열을 from과 to에 들어가도록 하였다.
그리고 merge 함수를 통해 from 키에 있던 모든 요소들을 to에 넣는다.
이때 from 폴더는 사라져야 하기 때문에 map에서 from 키를 삭제해줘야 한다.
// 반환 -> (파일의 집합,파일의 개수), 매개변수 -> 폴더 이름
pair<set<string>,int> dp(string folder){
// 이미 해당 폴더 이름의 dp배열에 할당된 값이 있다면 그 값을 사용
if(!(d[folder].first.empty() && d[folder].second == 0)) return d[folder];
int file = 0; // 파일의 개수
set<string> s; // s 값
// 해당 folder 내부에 있는 모든 요소들 검사
for(auto it : m[folder]){
// 파일일 경우
if(it.second == 0) {
// 파일의 개수 +1 하고 set에 넣음
s.insert(it.first);
file++;
}
// 폴더일 경우
else {
// 해당 폴더이름으로 dp 호출
// 그 반환값을 set과 file에 담음
pair<set<string>,int> val = dp(it.first);
file += val.second;
for(auto it : val.first) s.insert(it);
}
}
// 반환과 동시에 dp에 담음
return d[folder] = make_pair(s,file);
}
cin >> Q;
for(int i = 0; i < Q; i++){
string word;
cin >> word;
stringstream ss(word);
string tmp;
while(getline(ss,tmp,'/'));
// 종류, 개수
cout << dp(tmp).first.size() << " " << dp(tmp).second << "\n";
}dp의 반환값은 두 가지로 set과 int이다.
set으로 한 이유는 파일의 종류를 받아줘야 하기 때문에 중복을 제거하기 위해서이다.
매개변수로는 folder의 이름이 들어간다.
일반적인 dp와 같이 이미 값이 들어있다면 그 값을 사용하고 반환한다.
그 이외에는 위에서 설명했듯이, 매개변수 이름을 키로 가지는 map을 호출한다.
즉 해당 폴더 내부의 요소들을 모두 검사하여 파일이면 set에 넣고 파일개수 +1,
폴더이면 해당 폴더이름의 재귀함수를 호출한다.
그리고 그 반환값을 모두 이용하여 결과를 구한다.
그 결과를 d [매개변수 이름]에 저장시키는 것이다.
이렇게 하면 메모라이징 기법을 사용하여 연산의 횟수를 줄일 수 있다.
여기까지가 부분적인 설명의 끝이고, 이제 아래에 전체 코드를 올리고 마치겠다.
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <set>
#include <sstream>
using namespace std;
map<string,set<pair<string,int>>> m;
map<string,pair<set<string>,int>> d;
int N,M,K,Q;
void merge(string from, string to){
for(auto it : m[from]) m[to].insert(it);
m.erase(from);
}
// 반환 -> (파일의 집합,파일의 개수), 매개변수 -> 폴더 이름
pair<set<string>,int> dp(string folder){
// 이미 해당 폴더 이름의 dp배열에 할당된 값이 있다면 그 값을 사용
if(!(d[folder].first.empty() && d[folder].second == 0)) return d[folder];
int file = 0; // 파일의 개수
set<string> s; // s 값
// 해당 folder 내부에 있는 모든 요소들 검사
for(auto it : m[folder]){
// 파일일 경우
if(it.second == 0) {
// 파일의 개수 +1 하고 set에 넣음
s.insert(it.first);
file++;
}
// 폴더일 경우
else {
// 해당 폴더이름으로 dp 호출
// 그 반환값을 set과 file에 담음
pair<set<string>,int> val = dp(it.first);
file += val.second;
for(auto it : val.first) s.insert(it);
}
}
// 반환과 동시에 dp에 담음
return d[folder] = make_pair(s,file);
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
// N+M만큼 반복
for(int i = 0; i < N+M; i++){
string a,b;
int offset; // 폴더인지 파일인지
cin >> a >> b >> offset;
m[a].insert({b,offset}); // 상위폴더 set 컨테이너의 추가
d[a].second = 0; // a 이름을 가지는 key 생성
}
cin >> K;
for(int i = 0; i < K; i++){
string a,b;
cin >> a >> b;
stringstream ss1(a);
stringstream ss2(b);
string from,to;
while(getline(ss1,from,'/')); // 마지막 위치
while(getline(ss2,to,'/')); // 마지막 위치
merge(from,to);
}
cin >> Q;
for(int i = 0; i < Q; i++){
string word;
cin >> word;
stringstream ss(word);
string tmp;
while(getline(ss,tmp,'/'));
// 종류, 개수
cout << dp(tmp).first.size() << " " << dp(tmp).second << "\n";
}
}시행착오
폴더정리(small)를 풀고 난 후에 푸니까 어느 정도 풀만했던 것 같다.
문제 유형을 얼떨결에 들어서 풀었던 것 같기도 하고, 확실히 복잡했던 문제였다.
설명은 좀 많이 개떡같이 한 것 같은데..
코드로 잘 이해했으면 좋겠다..
처음으로 풀어본 골드 1 문제라서 기분은 좋다.
생활비..