[백준] (22861) 폴더 정리 (large) [Python]

문제 링크

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

문제

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

main
 ├─ FolderA
 │    ├─ File1
 │    └─ File2
 └─ FolderB
       ├─ FolderC
       │   ├─ File4
       │   └─ File5
       ├─ File1
       └─ File3

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

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

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

폴더 또는 파일을 옮겨 main 폴더를 정리하려고 한다.

예를 들어, FolderB 폴더 하위에 있는 두 개의 파일 File1, File3과 하나의 폴더 FolderC를 FolderA 폴더 하위에 옮기려고 한다.

File1 파일은 FolderA 폴더 안에 동일한 파일이 이미 존재하므로 덮어쓴다. File3은 동일한 파일이 없으므로 그대로 옮긴다. FolderC 폴더도 동일한 폴더가 없으므로 FolderA 폴더 하위에 옮긴다. FolderB 폴더 하위에 있는 폴더와 파일을 다 옮겼으므로 FolderB는 삭제한다.

아래는 FolderB 폴더를 FolderA 폴더 안에 옮긴 후 main 폴더의 하위 구조를 계층적으로 표시한 것이다.

main
 └─ FolderA
      ├─ FolderC
      │ ├─ File4
      │ └─ File5
      ├─ File1
      ├─ File2
      └─ File3

이러한 과정을 통해 폴더를 정리하려고 한다. 폴더 정리 후 쿼리를 통하여 파일의 정보를 확인하려고 한다.

---

코드

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent
        self.child = list()
        self.files = set()
    def add_child(self, child):
        self.child.append(child)
    def remove_child(self, child):
        if child in self.child:
            self.child.remove(child)
    def add_file(self, file):
        self.files.add(file)
    def remove_file(self, file):
        if file in self.files:
            self.files.remove(file)

class Tree:
    def __init__(self, root: Node):
        self.root = root

n, m = map(int, input().strip().split())
root = Node("main", None)
tree = Tree(root)
visited = set()
visited.add("main")

inputs = deque()
for _ in range(n+m):
    inputs.append(input().strip())

while inputs:
    st = inputs.popleft()
    arr = list(st.split())
    if arr[0] not in visited:
        inputs.append(st)
        continue
    visited.add(arr[1])
    if int(arr[2]) == 1: # Folder
        stack = list()
        stack.append(tree.root)
        while True:
            cur = stack.pop()
            if cur.value == arr[0]:
                break
            for c in cur.child:
                stack.append(c)
        child = Node(arr[1], cur)
        cur.add_child(child)
    else: # File
        stack = list()
        stack.append(tree.root)
        while True:
            cur = stack.pop()
            if cur.value == arr[0]:
                break
            for c in cur.child:
                stack.append(c)
        cur.add_file(arr[1])

def get_node_from_path(path):
    arr = list(path.split('/'))
    cur = tree.root
    for i in range(1, len(arr)):
        for j in range(len(cur.child)):
            if cur.child[j].value == arr[i]:
                break
        cur = cur.child[j]
    return cur

k = int(input().strip())
for _ in range(k):
    query = list(input().strip().split())
    src = get_node_from_path(query[0])
    dst = get_node_from_path(query[1])
    
    parent_src = src.parent
    parent_src.remove_child(src)
    
    for ch in src.child:
        dst.add_child(ch)
        ch.parent = dst
    for fi in src.files:
        dst.add_file(fi)
    del src

q = int(input().strip())
for _ in range(q):
    cur = get_node_from_path(input().strip())
    answer = defaultdict(int)
    for f in cur.files:
        answer[f] += 1
    for ch in cur.child:
        stack = list()
        stack.append(ch)
        while stack:
            curr = stack.pop()
            if curr.files:
                for f in curr.files:
                    answer[f] += 1
            if curr.child:
                for c in curr.child:
                    stack.append(c)

    print(len(answer), sum(answer[i] for i in answer))

 

폴더 정리 (small) 코드에서 폴더를 이동시키는 코드가 추가되었다. 그 외에 리팩토링 차원에서 get_node_from_path 함수를 작성한 것을 제외하면 이전 코드와 같다.

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