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

문제 (HashMap)

 

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

 

 

문제 풀이

 

문제를 꼼꼼하게 읽지 않아서 많이 애먹었다.

'main 하위 디렉토리에 같은 이름의 폴더가 두 개 이상 존재할 수 없다' ← 이 조건이 main바로 하위 폴더에만 적용되는 조건인 줄 알았는데 그게 아니라 전체 하위에 같은 이름의 폴더가 없다는 뜻이었나 보다.

그 말인 즉슨, '중복된 이름의 폴더는 없다' 라고 해석할 수 있는 것...^^

 

- main이 최상위 폴더로 고정되어 있음

- 중복된 폴더는 없음

- 폴더 및 파일 관계에 대한 input값은 순서 없이 랜덤하게 주어짐

 

이 조건만 잘 이해하고 풀었어도 시간이 이렇게 많이 걸리지는 않았을 텐데...

 

✅ 알고리즘

1. 각 폴더 별로 하위에 있는 폴더 및 파일을 담을 HashMap을 만든다.

  - main은 그냥 선언하면서 바로 만들어 주었다.

2. N + M개 반복을 돌면서 데이터를 Map에 담는다.

  - 상위 폴더, 본인 폴더 없을 경우를 if문으로 다 처리 해주어야 함

3. 쿼리를 받아 '/'으로 split하여 무조건 맨 뒤쪽 string을 넘겨서 카운트한다.

4. 카운트 함수는 재귀함수로 만들었다.

  - 폴더명을 받아서 하위 폴더를 더 이상 가지고 있지 않을 때까지 호출

  - 해당 폴더가 가진 파일map을 가져와서 count하고 set함수에 넣음

 

 

소스 코드

 

public class Main {
	
	static int count;
	static HashSet<String> set;
	static HashMap<String, ArrayList<String>> fileMap;
	static HashMap<String, ArrayList<String>> folderMap;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] param = br.readLine().split(" ");
		int N = Integer.parseInt(param[0]);
		int M = Integer.parseInt(param[1]);
		
		fileMap = new HashMap<>();
		folderMap = new HashMap<>();
		fileMap.put("main", new ArrayList<String>());
		folderMap.put("main", new ArrayList<String>());
		
		for(int i = 0; i < N + M; i++) {
			param = br.readLine().split(" ");
			String top = param[0];
			String cur = param[1];
			int folderYn = Integer.parseInt(param[2]);
			
			//폴더인 경우
			if(folderYn == 1) {
				if(!fileMap.containsKey(cur)) {
					folderMap.put(cur, new ArrayList<String>());
					fileMap.put(cur, new ArrayList<String>());
				}
				
				if(!folderMap.containsKey(top)) {
					folderMap.put(top, new ArrayList<String>());
					fileMap.put(top, new ArrayList<String>());					
				}
				
				ArrayList<String> list = folderMap.get(top);
				list.add(cur);
				folderMap.put(top, list);
			//파일인 경우
			}else {
				if(!folderMap.containsKey(top)) {
					folderMap.put(top, new ArrayList<String>());
					fileMap.put(top, new ArrayList<String>());					
				}
				ArrayList<String> list = fileMap.get(top);
				list.add(cur);
				fileMap.put(top, list);
			}
		}
		
		//쿼리 파일 개수 계산
		int Q = Integer.parseInt(br.readLine());
		for(int i = 0; i < Q; i++) {
			count = 0;
			set = new HashSet<>();
			String[] query = br.readLine().split("/");
			countFile(query[query.length - 1]);
			
			System.out.println(set.size() + " " + count);
		}
	}
	
	public static void countFile(String name) {
		ArrayList<String> folders = folderMap.get(name);
		if(folders == null) return;
		for(String folder: folders)
			countFile(folder);
		
		ArrayList<String> files = fileMap.get(name);
		if(files == null) return;
		for(String file: files) {
			count++;
			set.add(file);
		}
	}
}