[Java][BOJ 22860] 폴더 정리

문제 링크

문제 파악

main 폴더 하위에 있는 폴더의 총 개수 N, 파일의 총 개수 M

상위 폴더 이름 P, 폴더 또는 파일의 이름 F, 폴더면 1 파일이면 0

Q개의 쿼리는 main 부터 존재하는 경로에 대한 폴더인데, 폴더 하위에 있는 파일의 종류 개수와 파일의 총 개수를 출력하라

4 1
main FolderA 1
FolderA FolderB 1
FolderB FolderC 1
FolderC FolderD 1
FolderD File1 0
3
main
main/FolderA
main/FolderA/FolderB/FolderC/FolderD

출력

1 1
1 1
1 1

 

접근 방법

각 폴더마다 파일 Set로 중복 처리하고, Parent - Folder(File) 리스트를 dfs 탐색하면서 파일 개수 카운트

1. 부모 폴더에 따라 존재하는 파일을 set에 넣고, 파일 개수는 fileCnt 카운트

2. 쿼리에 따라 dfs 탐색 -> list 반환

하려고 했는데 dfs에서 각 folder에 해당하는 파일 종류를 추가하는 구조라서 main을 검색할때 다시 하위 폴더 반복문을 돌면서 set을 다시 만들어야 했다. -> return으로 main 밑에 달린 파일 전체를 반환하고 받아서 set으로 파일 종류를 세는게 더 효율적이다.  

3. 

코드 구현

인텔리제이는 개행 문자 없어서 무한루프나고, 백준에서는 NullPointer나는 내 코드

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

public class Main {
    static Map<String, List<String>> file_cnt = new HashMap<>();
    static List<String> ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int folder = Integer.parseInt(st.nextToken());
        int file = Integer.parseInt(st.nextToken());

        // folder 별 리스트 생성
        for (int i = 0; i < folder + file; i++) {
            st = new StringTokenizer(br.readLine());
            String parent = st.nextToken();
            String child = st.nextToken();
            int isFolder = Integer.parseInt(st.nextToken());

            file_cnt.putIfAbsent(parent, new ArrayList<>());
            file_cnt.get(parent).add(child);

            if (isFolder == 1) {
                // 자식 폴더의 리스트도 생성
                file_cnt.putIfAbsent(child, new ArrayList<>());
            }
        }

        // st는 한 줄 단위 토큰 파서라서 br 직접 사용
        int q = Integer.parseInt(br.readLine());


        // while(sc.hasNext()){
        for (int i = 0; i < q; i++) {
            // 찾아야 하는 폴더명: find
            String path = br.readLine();
            // sc.nextLine 사용시 마지막 개행 인식 오류 때문에 무한루프
            List<String> ans = new ArrayList<>();
            Set<String> ans_set = new HashSet<>();

            String[] parts = path.split("/");
            String find = parts[parts.length - 1];

            // 폴더마다 연결된 파일 개수와 종류 카운트
            // file 만 달린 리스트에서 Set으로 종류 구하기
            ans = new ArrayList<>();

            dfs(find);
            ans_set = new HashSet<>(ans);

            System.out.println(ans_set.size() + " " + ans.size());
        }
    }

    // 해당 폴더(key) 아래 파일 list 반환
    static void dfs(String folder) {
        if (! file_cnt.containsKey(folder)) return;

        for (String child : file_cnt.get(folder)) {
            // 폴더면 dfs
            if (file_cnt.containsKey(child)) {
                dfs(child);
            } else {
                ans.add(child);
            }
        }
    }
}

밑은 통과코드 뭐가 다른걸까

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

public class Main {
    static Map<String, List<String>> fileTree = new HashMap<>();
    static int fileCount;
    static Set<String> fileTypes;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int folder = Integer.parseInt(st.nextToken());
        int file = Integer.parseInt(st.nextToken());

        for (int i = 0; i < folder + file; i++) {
            st = new StringTokenizer(br.readLine());
            String parent = st.nextToken();
            String child = st.nextToken();
            int isFolder = Integer.parseInt(st.nextToken());

            fileTree.putIfAbsent(parent, new ArrayList<>());
            fileTree.get(parent).add(child);

            if (isFolder == 1) {
                fileTree.putIfAbsent(child, new ArrayList<>());
            }
        }

        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; i++) {
            String[] path = br.readLine().split("/");
            String folderName = path[path.length - 1];

            fileCount = 0;
            fileTypes = new HashSet<>();
            dfs(folderName);

            System.out.println(fileTypes.size() + " " + fileCount);
        }
    }

    static void dfs(String folder) {
        if (!fileTree.containsKey(folder)) return;

        for (String child : fileTree.get(folder)) {
            if (fileTree.containsKey(child)) {
                dfs(child);
            } else {
                fileTypes.add(child);
                fileCount++;
            }
        }
    }
}

배운점

    // 해당 폴더(key) 아래 파일 list 반환
    static List<String> dfs(String key, List<String> File, List<String> ing) {
        List<String> ans = ing;

        if(File.isEmpty()) return ans;

        for (String child : File) {
            if (child.contains("File")){
                ans.add(child);
            } else dfs(child, file_cnt.get(child), ans);
        }

        return ans;
    }
}

 

재귀를 만들긴 했는데 이해하기 너무 어렵다. 그래서 지피티가 바꾸라는 대로 바꿨따. 

 

질문

Intellij에서 입력 마지막 줄에 개행문자(\n)가 없어서, Scanner.nextLine()이 계속 기다리는 상황이라 프로그램이 안 끝난다. 

// while(sc.hasNext()){
        for (int i = 0; i < q; i++) {
            // 찾아야 하는 폴더명: find
            String path = sc.nextLine();
            // Line 사용시 마지막 개행 인식 오류 때문에 무한루프

sc.nextLine()을 사용하면 (\n)을 기준으로 한 줄을 받는데, 마지막 줄에는 개행문자가 없어서 무한루프. 공백도 없어서 next()도 인식을 못한다.

4 1 (\n)
main FolderA 1 (\n)
FolderA FolderB 1 (\n)
FolderB FolderC 1 (\n)
FolderC FolderD 1 (\n)
FolderD File1 0 (\n)
3 (\n)
main (\n)
main/FolderA (\n)
main/FolderA/FolderB/FolderC/FolderD

그래서 bufferReader로 바꿨는데도 내가 직접 엔터 쳐야만 마지막 답을 낸다. 왜이럴까??