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

December 27, 2023

ALGORITHM

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

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

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

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

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

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

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

접근

처음 문제를 봤을 때 학부시절떄 구현했던 파일 시스템이 기억이 났고, 문제 자체도 재밌어보였다. 코딩테스트를 볼 떄 간간히 볼 수 있었던 유형이였고, 문제를 볼때마다 어려움을 겪었던 기억이 있어서 신나게 도전해보았다.

문제를 파악해보자면 directory 경로가 주어지고, file인지 directory인지 구분하는 flag, 그리고 최종적으로 Query 가 들어오면 해당 Query의 디렉터리에 총 파일의 개수, 파일의 종류의 수를 출력을 요구하고 있다.

이 때 폴더는 폴더와 파일을 가질 수 있고, 파일은 자기 자체로만 존재하기 때문에 폴더라는 상위 객체를 만들고, 폴더나 파일을 추가하는 메서드를 추가하면 쉽게 처리할 수 있겠다고 판단했다.

그렇게 해서 Directory라는 class를 생성했다.


class Directory {
	constructor() {
		this.directories = new Map();
		this.files = new Set();
	}

	addDirectory(dirName) {
		const directory = directoryMap.get(dirName);
		this.directories.set(dirName, directory);
	}

	addFile(fName) {
		this.files.add(fName);
	}
}

Directory는 파일을 추가하고, 폴더를 추가하는 메서드를 갖고 있다. 문제를 풀고 제출하면서 알게된 사실은 입력이 순서대로 주어지지 않는다는 것 이었다. 이는 실제 세상을 어느정도 반영했다는 생각이 든다. 이 블로그를 개발할 때에도 build 시점에 routes에 대한 directory를 생성해주지 않으면 정적인 페이지가 만들어지지 않았던 문제가 있었듯이 이러한 스트레스 케이스를 추가헤준듯 하다.

떄문에 이러한 문제를 처리해주기 위해 미리 경로에 대한 폴더들을 생성해주었다.


for (let i = 1; i <= N + M; i++) {
	const [P, F, C] = input[i].split(' ');

	if (!directoryMap.has(P)) directoryMap.set(P, new Directory());

	if (Number(C) === 1 && !directoryMap.has(F)) {
		directoryMap.set(F, new Directory());
	}
}

이렇게 해서 파일 시스템 상에 존재하는 모든 디렉터리를 미리 생성해주었고, 이를 directoryMap에서 관리하여 언제든지 참조할 수 있게 구현했다.

다음은 총 파일의 개수를 구하는 부분이다. 처음에는 매번 해당 디렉터리로 가서 재귀적으로 해당 디렉터리 하위 디렉터리에 총 몇개의 파일이 존재하는지 매번 검사를 수행했다.


// Directory 클래스의 메서드
  getTotalFiles() {
    let count = this.files.size;
    const set = new Set([...this.files]);

    for (const dirKey of this.directories.keys()) {
      const dir = directoryMap.get(dirKey);
      const result = dir.getTotalFiles();

      count += result.count;
      result.set.forEach((file) => {
        set.add(file);
      });
    }

    return {
      count,
      set,
    };
  }

하지만, 이렇게 하면 시간초과가 터져버렸다. 이유는 하위 경로의 파일 개수를 구하는 동작이 중복되기 떄문에 입력이 커지면 커질수록 중복된 연산으로 인한 비용이 기하급수적으로 증가하기 떄문이였다.

때문에 이를 한 번 처리하고, 미리 계산한 결과를 바탕으로 최종 결과를 이끌어내는 Memoization을 활용하면 최적화가 가능할 것 으로 판단했다.

위 로직을 고쳐보자면, 상위 디렉터리는 자신이 갖고 있는 하위 디렉터리를 재귀적으로 검사하여 총 파일의 개수를 측정하고자 한다. 때문에, root 디렉터리인 main 디렉터리에서 getTotalFiles 메서드를 실행한다면 하위 디렉터리의 총 파일 개수를 모두 한 번에 구할 수 있다.


  getTotalFiles() {
    let count = this.files.size;
    const set = this.files;

    for (const dir of this.directories.values()) {
      const result = dir.getTotalFiles();

      count += result.count;
      result.set.forEach((file) => {
        set.add(file);
      });
    }

    this.count = count;

    return {
      count,
      set,
    };
  }

이렇게 수정하고 해당 Directory 객체에 count 값을 추가해주면 모든 디렉터리들의 자신이 갖고 있는 파일의 개수를 저장시킬 수 있었고 이로써 정답을 받을 수 있었다.

코드


class Directory {
	constructor() {
		this.directories = new Map();
		this.files = new Set();
	}

	addDirectory(dirName) {
		const directory = directoryMap.get(dirName);
		this.directories.set(dirName, directory);
	}

	addFile(fName) {
		this.files.add(fName);
	}

	getTotalFiles() {
		let count = this.files.size;
		const set = this.files;

		for (const dir of this.directories.values()) {
			const result = dir.getTotalFiles();

			count += result.count;
			result.set.forEach((file) => {
				set.add(file);
			});
		}

		this.count = count;

		return {
			count,
			set,
		};
	}
}

const [N, M] = input[0].split(' ').map(Number);
const directoryMap = new Map();
const main = new Directory();

directoryMap.set('main', main);

for (let i = 1; i <= N + M; i++) {
	const [P, F, C] = input[i].split(' ');

	if (!directoryMap.has(P)) directoryMap.set(P, new Directory());

	if (Number(C) === 1 && !directoryMap.has(F)) {
		directoryMap.set(F, new Directory());
	}
}

for (let i = 1; i <= N + M; i++) {
	const [P, F, C] = input[i].split(' ');
	const directory = directoryMap.get(P);

	if (Number(C) === 1) {
		// F는 Directory
		directory.addDirectory(F);
	} else {
		// F 는 file
		directory.addFile(F);
	}
}

main.getTotalFiles();

for (let i = N + M + 2; i < input.length; i++) {
	const query = input[i].split('/');

	const dir = directoryMap.get(query.at(-1));

	console.log(dir.files.size, dir.count);
}