[백준] 22860번 폴더 정리(small)

U_U·2024년 2월 28일

22860 22860번 폴더 정리(small)boj 구현 백준 코딩테스트 폴더 정리(small)

문제 - 폴더 정리 (small)

https://www.acmicpc.net/problem/22860

문제

이름이 main 폴더 안에 여러가지 파일과 폴더가 존재한다.

main
├─ FolderA
│ ├─ File1
│ └─ File2
└─ FolderB
├─ FolderC
├─ File1
└─ File3
위 구조는 main 폴더의 하위 구조를 계층적으로 표시한 것이다. FolderA, FolderB, FolderC는 폴더이고 File1, File2, File3은 파일이다. 파일 이름이 같은 경우는 동일한 파일이다.

한 폴더 안에는 같은 이름의 파일이 두 개 이상 존재할 수 없다.

main 하위 디렉토리에 같은 이름의 폴더가 두 개 이상 존재할 수 없다.

폴더 정리를 하기 위해 main 폴더 하위에 있는 파일들을 확인하려고 한다.

주어지는 쿼리에 대해 폴더와 파일의 정보를 알려주는 프로그램을 만들어보자.

입력

첫 번째 줄에는 main 폴더 하위에 있는 폴더의 총 개수
$N$ 과 파일의 총 개수
$M$ 이 공백으로 구분되어 주어진다.

두 번째 줄부터
$N + M + 1$ 번째까지 상위 폴더의 이름
$P$ , 폴더 또는 파일의 이름
$F$ , 폴더인지 아닌지 알려주는
$C$ 가 공백으로 구분되어 주어진다.

$C$ 의 값은
$F$ 가 폴더라면 1, 파일이라면 0으로 주어진다.

$N + M + 2$ 번째 줄에는 쿼리의 개수
$Q$ 가 주어진다.

그 다음줄부터
$Q$ 개의 쿼리가 주어진다. 쿼리마다 main부터 폴더의 경로 정보가 들어온다. 예를 들어 main 폴더 안에 FolderB에 대한 쿼리가 들어온다면, FolderB의 경로인 main/FolderB로 주어진다. 반드시 폴더가 존재하는 경로로 주어짐을 보장한다.

출력

쿼리 순서대로 한 줄씩 폴더 하위에 있는 파일의 종류의 개수와 파일의 총 개수를 출력한다.

파일의 종류의 개수는 같은 파일이 여러개 있을 경우 하나로 계산한다. 파일의 총 개수는 같은 파일이 있더라도 하나로 계산하지 않는다.

예를 들어 이름이 File1 파일이 5개가 있을 경우 파일의 종류는 1 가지이고 파일의 총 개수는 5개이다.

접근방법

파일과 하위 폴더를 가고 있는 객체를 만들어서 구조를 갖춰가는 방식

이 문제를 처음 봤을 때, 폴더가 가지고 있어야 하는 정보가 parent인가, child인가에 대해 생각해보았다. 결론적으로 하위폴더들에 있는 file을 가져와야하기 때문에 폴더의 child를 모아두는 곳이 필요하다고 생각해서 그냥 객체를 만들었다.
그래서 내가 만든 객체는 다음과 같다.

Folder 객체

	static class Folder{
		String name;  // 폴더이름
		ArrayList<Folder> child = new ArrayList<>(); //하위폴더목록
		ArrayList<String> file = new ArrayList<>();  // 파일 목록
		Folder(){
			
		}
		Folder(String name){
			this.name = name;
		}
	}

정답코드

import java.util.*;
import java.io.*;
public class Main {
	
	static int N;
	static int M;
	static int diff;
	static int many;

	static class Folder{
		String name;
		ArrayList<Folder> child = new ArrayList<>();
		ArrayList<String> file = new ArrayList<>();
		Folder(){
			
		}
		Folder(String name){
			this.name = name;
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String [] strs = br.readLine().split(" ");
		
		ArrayList<Folder> folder = new ArrayList<>();
		
		HashMap<String, Integer> indexFolder = new HashMap<>();  // Folder 이름 : 인덱스 
 		
		N = Integer.parseInt(strs[0]);
		M = Integer.parseInt(strs[1]);
		
		Folder root = new Folder("main");
		folder.add(root);
		indexFolder.put("main", 0);
		for(int i=0;i<N+M;i++) {
			strs = br.readLine().split(" ");
			String P = strs[0];
			String F = strs[1];
			int C = Integer.parseInt(strs[2]);
			if(C == 1) {
				Folder now = null;
				for(int j=0;j<folder.size();j++) {
					if(folder.get(j).name.equals(F)) {
						now = folder.get(j);
						break;
					}
				}
				if(now == null) {
					now = new Folder(F);
					folder.add(now);
					indexFolder.put(F, folder.size()-1); // 텅 빈 폴더를 만들고 
				}
				
				Folder parent = null;

				if(indexFolder.get(P)==null) {
					parent = new Folder(P);
					folder.add(parent);
					indexFolder.put(P, folder.size()-1); // 텅 빈 폴더를 만들고 
				}
				else {
					int index = indexFolder.get(P);
					parent = folder.get(index);
				}

				parent.child.add(now);  //이름으로 -> 인덱스를 찾아서 -> 부모 폴더를 찾아서 -> child에 추가 
				
			}
			else if(C == 0) {
				Folder parent = null;

				if(indexFolder.get(P)==null) {
					parent = new Folder(P);
					folder.add(parent);
					indexFolder.put(P, folder.size()-1); // 텅 빈 폴더를 만들고 
				}
				else {
					int index = indexFolder.get(P);
					parent = folder.get(index);
				}
				parent.file.add(F); // 이름으로 -> 인덱스를 찾아서 -> 부모 폴더를 찾아서 ->file에 추가 
				
			}
		}

		
		int Q = Integer.parseInt(br.readLine());
		for(int i=0;i<Q;i++) {
			many =0;
			HashSet<String> diff = new HashSet<>();
			strs = br.readLine().split("/");
			int index = indexFolder.getOrDefault(strs[strs.length-1], -1);
			if (index == -1) {
			    continue;
			} else {
			    Folder find = folder.get(index);
			    findFolder(find, diff);
			    System.out.println(diff.size() + " " + many);
			}

		}
		
	}
	public static void findFolder(Folder find, HashSet<String> diff) {
		many +=find.file.size();
		for(String s : find.file) {
			diff.add(s);
		}
		if(find.child.size()!=0) {
			for(Folder f : find.child)
				findFolder(f,diff);
		}
	}

}