(백준 22860 폴더 정리 (small)

• tags : (algorithm

  No matching post could be found

  - (trie
• 문제 링크 : https://www.acmicpc.net/problem/22860
• 풀이 링크
  • Python

• 폴더, 파일을 구조화하는 문제
  • 각 폴더별 하위 폴더의 파일에 대한 쿼리를 해결해야 한다.
• 각 폴더 이름이 중복으로 나오지 않아서 (백준 14725 개미굴

  No matching post could be found

  문제와는 다르게 트라이 구조의 각 노드 값을 신경쓸 필요가 없다.
  • 하지만 파일 이름은 중복으로 나올 수 있다.
  • 파일은 각 노드를 이루지 않아서 크게 신경 쓸 필요는 없지만, 각 폴더가 포함한 파일을 중복없이 세기 위하여 set을 활용했다.

• Python 풀이를 dataclass를 활용했다.
  • trie구조를 클래스로 구현할 수 있지만, dataclass를 적용해보기위해 조금 독특하게 구성해보았다.

@dataclass
class Directory:
    parent: str
    files_count: int = 0
    files: set = field(default_factory=set)

    def get_different_files_count(self) -> int:
        return len(list(self.files))

• dataclass는 각 노드를 이루도록 구성했고,
  • 인자로 부모, 각 폴더 이하에 속한 파일의 종류와 파일의 수를 기록했다.
• 또한 파일 이름을 set에 저장해두어, 서로다른 파일의 수를 출력하기 위한 메서드도 작성했다.

def add_folder(F: str, parent: str, child: str) -> None:
    global directory, folder_to_directory
    directory[child] = Directory(parent=parent)
    folder_to_directory[F] = child

def add_file(folder_name: str, file_name: str) -> None:
    global directory
    directory[folder_name].files.add(file_name)
    directory[folder_name].files_count += 1

• 폴더 구조, 파일 구조를 수정하는 함수는 다음과 같다.
  • 폴더의 경우, 자식 폴더에서 부모 폴더를 지정해준다.
  • 파일의 경우 파일 추가 및 파일의 수를 추가한다.

for _ in range(N + M):
    P, F, C = input().strip().split()
    if P == "main":
        if C == "0":
            add_file(parent_directory, F)
            folder_to_directory[F] = parent_directory
        else:
            child_directory = f"{parent_directory}/{F}"
            add_folder(F, parent_directory, child_directory)
    else:
        if C == "0":
            files.append((P, F))
        else:
            folders.append((P, F))

• 이 방식의 풀이는 한가지 단점이 있는데, main폴더부터 하위 폴더로 입력되는것을 기준으로 작성했었다.
• 따라서 main폴더에 속하는 폴더 또는 파일만 우선 처리했다.
  • 만약 속한다면, 위의 두 함수를 활용해서 폴더 및 파일을 추가한다.
• main폴더가 부모가 아니라면 files, folders라는 deque를 미리 생성해두었고, 폴더, 파일만 구분하여 저장했다.
  • 각 폴더 및 파일은 main이 부모일때와 유사하게 처리했다.

def update_files(folder_name: str, file_name: str) -> None:
    global directory
    while folder_name != "main":
        parent = directory[folder_name].parent
        directory[parent].files.add(file_name)
        directory[parent].files_count += 1
        folder_name = parent

• 각 파일을 추가할때는 위의 함수를 활용했다.
  • 해당 파일의 부모를 불러가며 파일 추가 및 파일 개수를 더했다.