[Baekjoon 22860] 폴더 정리

문제

💛Ⅲ [Baekjoon 22860 - 폴더 정리]

문제 풀이 방법

전형적인 구현문제라고 생각하고, 폴더의 자료구조를 dictionary로 만들어야 검색이 빠를 것이라고 생각하였다.

1. 입력을 받으면서 폴더이름을 key로 하는 dictionary를 구성한다.
2. 쿼리를 입력받아 searchDic함수로 검색한다.
   1. dictionary에 폴더이름을 검색하고 그 안에 폴더가 또 존재한다면 자신의 재귀호출한다.
   2. 그 안에 폴더가 존재하지 않는다면 파일 배열에 파일을 추가하고 종료한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

def searchDic(dic, file, name):
    for x in dic[name]:
        if x[1] == '0':
            file.append(x[0])
        else:
            searchDic(dic, file, x[0])
    return

directory = {}

N, M = map(int, input().split())
for _ in range(N+M):
    tmp = input().split()
    if tmp[0] in directory:
        directory[tmp[0]].append([tmp[1], tmp[2]])
    else:
        directory[tmp[0]] = [[tmp[1], tmp[2]]]
    if tmp[2]=='1' and tmp[1] not in directory:
        directory[tmp[1]] = []

Q = int(input())
queries = [input().rstrip().split('/') for _ in range(Q)]

for query in queries:
    files = []
    for x in directory[query[-1]]:
        if x[1] == '0':
            files.append(x[0])
        else:
            searchDic(directory, files, x[0])
    print(len(set(files)), len(files))