백준 22861번 : 폴더 정리(Large)

문제 : https://www.acmicpc.net/problem/22861

 

문제의 조건을 이해하는 것이 문제입니다.

 

저는 천천히 문제를 읽으면서, 어떤 기능이 필요할지 정리를 먼저 했습니다. 

 

1. 폴더와 파일의 처음 입력값에 대해.

초기 폴더 계층 구조를 문제에서 주어질 때, 2가지의 경우가 있습니다. 1) 폴더에 파일 넣기, 2) 폴더에 폴더 넣기

 

2. 특정 폴더를 다른 폴더의 하위로 옮기기

이 과정에서 주요한 조건은 "하나의 폴더에 동일한 파일의 이름이 존재할 수 없다"입니다. 

 

3. 특정 폴더의 파일의 수 및 파일의 종류를 구하기

 

이를 바탕으로, 폴더라는 클래스를 생성했습니다. 

 

Class Folder

- Set<String> subFolder

- Set<String> subFiles

 

 "하나의 폴더에 동일한 파일(폴더)의 이름이 존재할 수 없다"의

 

"2. 특정 폴더를 다른 폴더의 하위로 옮기기" 과정은 A폴더를 B폴더로 이동시킨다고 가정하면, A 폴더의 subFolder와 subFiles를 B 폴더로 모두 쏟아주면 됩니다. 단! 여기서 중요한 점은 A폴더의 상위 폴더 C 가 존재한다면, C 폴더의 subFolder에서 A폴더를 제거해주어야 합니다.

문제의 입력값을 보면 친절하게도 "A의 촤상위 폴더/A 상위 폴더/.../A폴더" 형태로 주어지기 때문에, 쉽게 A의 상위 폴더에서 A 폴더 이름을  O(1)로 삭제할 수 있습니다. 

 

마지막으로 위 클래스 설계를 통해 "3. 특정 폴더의 파일의 수 및 파일의 종류를 구하기"를 구해 낼 수있는지가 중요합니다.  특정 폴더 A에 대해 파일의 수는 subFiles의 size + subFolder의 Folder의 subFiles의 size의 총합으로 구할 수 있습니다. 위 과정을 진행하며, 모든 subFiles를 하나의 Set에 넣어준다면, 파일의  종류 또한 구해낼  수 있습니다.

 

+ 저는 HashMap<String, Folder> folderName이라는 자료구조를 통해, 각 Folder를 주어진 이름을 통해 각 객체를 구분하기 쉽게 하였습니다. 

 

package HiJaeYoung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Num22861폴더정리 {
    private static class Folder{
        String parentFolder; // 얜 필요없습니다.
        Set<String> subFolders;
        Set<String> files;
        Folder(){
            subFolders = new HashSet<>();
            files = new HashSet<>();
        };
        public void remove(String subFoldersName){
            subFolders.remove(subFoldersName);
        }
        public void addSubFolder(Folder folder){
            this.subFolders.addAll(folder.subFolders);
            this.files.addAll(folder.files);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        HashMap<String,Folder> folderName = new HashMap<String, Folder>();
        for(int i=0;i<n+m;i++){
            st = new StringTokenizer(br.readLine());
            String name1 = st.nextToken();
            String name2 = st.nextToken();
            String type = st.nextToken();
            if(type.equals("1")){
                if(!folderName.containsKey(name1)){
                    folderName.put(name1,new Folder());
                }
                folderName.get(name1).subFolders.add(name2);
                if(!folderName.containsKey(name2)){
                    folderName.put(name2,new Folder());
                }
                folderName.get(name2).parentFolder = name1;
            }
            if(type.equals("0")){
                if(!folderName.containsKey(name1)){
                    folderName.put(name1,new Folder());
                }
                folderName.get(name1).files.add(name2);
            }
        }
        int k = Integer.parseInt(br.readLine());
        for(int i = 0;i<k;i++){
            st = new StringTokenizer(br.readLine());
            String[] suFolder = st.nextToken().split("/");
            if(suFolder.length >1){
                folderName.get(suFolder[suFolder.length-2]).remove(suFolder[suFolder.length-1]);
            }
            String[] parentFolder =st.nextToken().split("/");
            folderName.get(parentFolder[parentFolder.length-1]).addSubFolder(folderName.get(suFolder[suFolder.length-1]));
        }
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<q;i++){
            int fileNumber = 0;
            Set<String> files = new HashSet<>();
            String[] query = br.readLine().split("/");
            Queue<String> que = new LinkedList<>();
            que.add(query[query.length-1]);
            while(!que.isEmpty()){
                String nowFolder = que.poll();
                Folder folder = folderName.get(nowFolder);
                fileNumber += folder.files.size();
                files.addAll(folder.files);
                que.addAll(folder.subFolders);
            }
            sb.append(files.size()).append(" ").append(fileNumber).append("\n");
        }
        System.out.print(sb);
    }
}