1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/22860

(1) 조건 분석 📊

문제에서 요구하는 폴더의 하위 파일 종류와 개수를 출력하라.

main 폴더 아래 같은 이름의 폴더는 2개 이상 존재할 수 없다.
한 폴더는 자신의 레벨에서 같은 이름의 파일을 두 개 이상 가지지 못한다.
```bash

-- 불가능 예시
FolderA
ㄴfile1
ㄴfile1


# 2. 코드가 나오기까지 🛠️
**`KEY WORD`: `자료구조`, `유니온파인드`**  

## (0) 자료 구조 세팅
해당 문제는 다음과 같은 이유로 HashMap 3개와 유니온 파인드용 `parents` 배열이 필요하다.

1. 폴더 이름만 주어진다. 폴더 이름으로는 index 활용 풀이가 어렵다.
    - 계층 구조 표현 및 유니온 파인드 구현을 위해서는 노드마다 번호를 붙이는 것이 수월하다. 따라서 다음과 같이 HashMap을 이용해 번호를 붙인다.
    - key = 폴더 이름, value = 폴더 번호
    - key = 파일 이름, value = 파일 번호
    - key = 폴더 이름, value = HashSet(하위 디렉토리 포함 자신이 보유한 파일의 번호들)
2. 유니온 파인드와 자신이 보유한 누적 파일 개수를 위한 배열도 두 개 만든다.

## (1) 입력 처리하기 - 유니온 파인드
문제에서 나오는 입력 명령어는 두 가지 이다.
```bash
명령어 1 - 부모 폴더 이름 | 자식 폴더 이름 | 1
명령어 2 - 폴더 이름 | 파일 이름 | 0

만약 명령어 1인 폴더의 부모 자식 관계 산정이면, 유니온파인드를 진행해서, 부모와 자식을 트리 구조로 이어야 한다. 여기서 중요한 점은 경로압축을 하면 안된다. 이유는 명령어 2 때문이다.
명령어 2가 실행되는 시점이 되면, 주어진 폴더 이름을 포함해서, 그것의 모든 상위 폴더에 파일 개수 +1, 현재 파일 유형이 신규 파일 유형이면 + 1 을 추가한다.

(2) 쿼리 처리하기

리프 노드 폴더 빼고는 다 필요 없다. 따라서 br.readLine().split("\") 으로 맨 마지막 폴더 이름만 쓰고 나머지는 버린다.

(1) 시간복잡도 분석 ⏳

N과 M이 1000개밖에 안된다.
일자형 트리이고, 리프노드에 파일을 전부 넣는다고 하더라도

폴더를 거슬러 올라가며 파일 개수 및 파일 유형을 업데이트 하는데 총 $1,000 \times 1,000 = 1,000,000$ 번의 연산 횟수 밖에 들지 않는다.

3. 코드 🌐

import java.io.*;  
import java.util.*;  

/*  
* 폴더 정리 (small)* 1. 폴더와 파일 입력으로 unionfind 만들기 -> 경로 압축하지 말기  
* 2. 파일 입력 시 부모 노드 타고 가며 + 1씩 다 해주기  
* */  

public class Main {  
    static HashMap<String, Integer> folders = new HashMap<>(); // <폴더_이름, 폴더 번호>  
    static HashMap<String, Integer> files = new HashMap<>(); // <파일_유형, 파일 번호>  
    static HashMap<Integer, HashSet<Integer>> per_folder_file_cnt = new HashMap<>(); // <폴더 번호, 보유 파일 번호>  
    static int [] parents; // index  = 폴더 번호, value = 부모 폴더 번호 (처음엔 자기 자신을 가리킴)  
    static int [] accFiles; // 자기 하위 누적 파일 수  
    static int N,M,Q; // 각각 폴더의 개수, 파일의 개수  
    static int folder_counter = 1;  
    static int file_counter = 1;  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());  
        M = Integer.parseInt(st.nextToken());  
        parents = new int [N+2];  
        accFiles = new int [N+2];  
        for(int i = 1; i <= N+1; i++){  
            parents[i] = i;  
            per_folder_file_cnt.put(i, new HashSet<>());  
        }  
        String [][] inputOrders = new String[N+M][3];  
        for (int i = 0; i < N+M; i++){  
            inputOrders[i] = br.readLine().split(" ");  
        }  

        Arrays.sort(inputOrders, (row1, row2) -> {  
            int row1_order = Integer.parseInt(row1[2]);  
            int row2_order = Integer.parseInt(row2[2]);  
            return row2_order - row1_order;  
        });  

        for (int i = 0; i < inputOrders.length; i++) {  
            if(inputOrders[i][2].equals("1")) setParents(inputOrders[i][0], inputOrders[i][1]);  
            else setAccFiles(inputOrders[i][0], inputOrders[i][1]);  
        }  

        Q = Integer.parseInt(br.readLine());  

        StringBuilder answer = new StringBuilder();  
        for(int i = 0; i < Q; i++){  
            String [] paths = br.readLine().split("/");  
            int folder_num = folders.get(paths[paths.length-1]);  
            answer.append(per_folder_file_cnt.get(folder_num).size()).append(" ").append(accFiles[folder_num]).append("\n");  
        }  
        System.out.println(answer);  
    }  

    public static void setParents(String parent, String child){  
        if(folders.getOrDefault(parent, 0) == 0){  
            folders.put(parent, folder_counter++);  
        }  
        if(folders.getOrDefault(child, 0) == 0) {  
            folders.put(child, folder_counter++);  
        }  
        int p_num = folders.get(parent);  
        int c_num = folders.get(child);  
        parents[c_num] = p_num;  
    }  

    public static void setAccFiles(String folder, String file){  
        if(files.getOrDefault(file, 0) == 0){  
            files.put(file, file_counter++);  
        }  
        int folder_num = folders.get(folder);  
        int file_num = files.get(file);  
        doAcc(folder_num, file_num);  
    }  


    public int find(int a){  
        if(a == parents[a]) return parents[a]; // 부모가 자기자신이라면 그것을 return        else return find (parents[a]);  
    }  

    public static void doAcc(int child, int file_type_num){  
        accFiles[child]++;  
        per_folder_file_cnt.get(child).add(file_type_num);  
        if(child == parents[child]) return;  
        doAcc(parents[child], file_type_num);  
    }  
}

4. 트러블 슈팅 or 배운 점📝

(1) 입력은 부모부터 자식까지 순서대로 오지 않는다.

Happy-case만 생각하는 습관 때문에 처음에 틀렸었다.
폴더 관계 명령어, 파일 삽입 명령어가 뒤죽박죽으로 올 수 있다. 필자는 폴더간의 관계 명령어가 있을 때, 폴더 번호를 만들어 썼음으로, 다음과 같이 파일 명령어가 앞에 다 몰려있을 경우, 만들어지지 않은 폴더를 사용하므로 Null-Pointer 에러가 났다.

3 4
FolderB File1 0
FolderB File3 0
FolderB FolderC 1
main FolderA 1
main FolderB 1
FolderA File1 0
FolderA File2 0
4
main
main/FolderA
main/FolderB
main/FolderB/FolderC

문제에서 '순서대로 주어진다.' 라는 말이 없으면 항상 위와 같은 edge-case를 조심해야할 것이다.