문제
22860번: 폴더 정리 (small) (acmicpc.net)
풀이
파일 구조를 보고 경로에 어떤 파일이 있는지 출력하는 문제이다. 어떤 자료구조를 사용해야 할지 먼저 고민했다.
제한 메모리가 1024MB로 충분히 컸기 때문에 다중 연결리스트를 써도 되지 않을까 생각했는데 폴더가 최대 1,000개인데 depth가 1,000인 연결 리스트를 만들어도 괜찮을지 모르겠다.
폴더이면 (C==1) 상위 폴더에 연결리스트를 추가한다.
파일이면 (C==0) 상위 폴더에 파일 번호를 추가한다.
일단 이렇게 아이디어를 떠올렸다.
생각해보니 새로 연결리스트를 만들어서 그 자리에 넣는 게 아니라 새로 만든 리스트의 주소를 넣어도 될 것 같다. 그게 그거긴 한 것 같다. 어차피 포인터를 넣는 거니까...? 그러니까 폴더마다 연결리스트를 만들고, 폴더 내에 파일 이름을 저장하는 구조. 폴더 내에 파일이 있다면 그 파일 주소를 저장하는 식.
쿼리를 통해 해당 폴더 안에 파일이 몇 개 있는지, 종류가 몇 개인지는 dp를 통해 찾는 걸로. 일일이 찾는 것보다 효율적이지 않을까?
현재까지 저장된 폴더 중 찾기
폴더가 이미 있다 -> 그 폴더를 현재 폴더로 설정 ->하위 폴더/파일을 추가
폴더가 없다 -> 폴더를 만들기 -> 하위 폴더/파일을 추가
자료구조로 리스트를 사용하는 접근 방법이 맞는지 도저히 확신이 들지 않아서 다른 풀이를 참고하다가 객체를 사용하는 아이디어가 있어서 바로 코드를 짜봤다.
Folder객체를 만들어 이름, 하위 폴더, 하위 파일을 가지도록 하고 입력 받는 대로 객체를 만들어서 하위 폴더/파일을 추가하여 폴더 구조를 만들었다.
import java.io.*;
import java.util.*;
public class Main {
static int fileCnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
List<Folder> folderList = new ArrayList<>();
HashMap<String, Integer> folderMap = new HashMap<>(); // 노드이름 : 부모노드 인덱스
folderList.add(new Folder("main"));
folderMap.put("main", 0);
for (int i = 0; i < N + M; i++) {
st = new StringTokenizer(br.readLine());
String P = st.nextToken();
String F = st.nextToken();
int C = Integer.parseInt(st.nextToken());
Folder now = null;
for (int j = 0; j < folderList.size(); j++) {
if (folderList.get(j).name.equals(P)) {
now = folderList.get(j); // 폴더가 이미 있는 경우
break;
}
}
if (now == null) { // 폴더가 없는 경우
now = new Folder(P);
folderList.add(now);
}
if (C == 1) { // 폴더 추가
Folder childFolder = new Folder(F);
now.childFolder.add(childFolder);
folderList.add(childFolder);
folderMap.put(F, folderMap.get(P));
} else if (C == 0) {
now.childFile.add(F); // 파일 추가
}
}
int Q = Integer.parseInt(br.readLine());
for (int i = 0; i < Q; i++) {
fileCnt = 0;
String[] str = br.readLine().split("/");
String nowName = "";
Folder nowFolder = null;
nowName = str[str.length - 1];
for (int j = 0; j < folderList.size(); j++) {
if (folderList.get(j).name.equals(nowName)) {
nowFolder = folderList.get(j);
HashSet<String> hs = new HashSet<>();
findFile(nowFolder, hs);
bw.write(hs.size() + " " + fileCnt + "\n");
}
}
}
bw.close();
}
static void findFile(Folder folder, HashSet<String> hs) {
fileCnt += folder.childFile.size();
for (String s : folder.childFile)
hs.add(s);
if (folder.childFolder.size() != 0) {
for (Folder f : folder.childFolder)
findFile(f, hs);
}
}
}
class Folder {
String name; // 폴더 이름
List<Folder> childFolder = new ArrayList<>(); // 하위 폴더
List<String> childFile = new ArrayList<>(); // 하위 파일
Folder(String name) {
this.name = name;
}
}그런데 이 코드는 입력값으로 파일 구조가 주어질 때, root부터 차례로 주어지지 않을 수도 있다는 사실을 간과하고 있다.
따라서 아직 정의되지 않은 폴더에 하위 폴더와 파일을 넣으려고 시도할 경우, 폴더를 찾지 못하게 되므로 하위 폴더와 파일이 추가되지 못하고 버려진다.
(반례)
1 1
FolderA File1 0
main FolderA 1
1
main
1 1 //정답
0 0 //출력값
그래서 먼저 전체 파일 구조를 받아서 hashmap에 저장해둔 뒤, root부터 차례로 파일 구조를 만들어야 한다.
아니면 부모노드가 아직 만들어지지 않았으면 그냥 부모노드 자리에 -1을 넣고 지나갔다가 나중에 밝혀지면 그 자리에 다시 넣으면 되지 않을까 생각했다.
하지만 그럴 필요 없이 무조건 P를 먼저 생성하도록 하고 F를 P의 하위에 추가하도록 하면 파일 구조의 순서와 상관 없이 입력받을 수 있다.
1. P가 없으면 새로 생성하여 folderList에 추가
2. C==1 : F가 없으면 새로 생성하여 folderList에 추가, P의 하위 폴더로 F를 추가
3. C==0 : P의 하위 파일로 F를 추가
이제 P객체가 없으면 생성하도록 했으므로, F의 부모인 P객체가 아직 만들어지지 않은 경우는 없다.
쿼리를 보고 파일 수, 파일 종류 수를 계산해야 하는데 왜 경로를 다 줬는지 모르겠다. substring을 써보라는 의도인지..? 그냥 폴더 이름만 줘도 충분하지 않을까?
파일 수, 파일 종류 수는 하위 폴더가 없을 때까지 findFile을 재귀호출하면서 구했다. 파일 종류 수는 같은 파일명을 하나로 카운트해야 하므로 HashSet을 썼다.
코드
import java.io.*;
import java.util.*;
public class boj_22860 {
static int fileCnt;
static List<Folder> folderList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
folderList = new ArrayList<>();
for(int i=0; i<N+M; i++){
st = new StringTokenizer(br.readLine());
String P = st.nextToken();
String F = st.nextToken();
int C = Integer.parseInt(st.nextToken());
Folder now = findFolder(P);
if(now==null){ //폴더가 없는 경우
now = new Folder(P);
folderList.add(now);
}
if(C==1) { //폴더추가
Folder folder = findFolder(F);
if(folder == null){
folder = new Folder(F);
now.childFolder.add(folder);
folderList.add(folder);
}else now.childFolder.add(folder);
}
else if(C==0){ //파일추가
now.childFile.add(F);
}
}
int Q = Integer.parseInt(br.readLine()); //쿼리
for(int i=0; i<Q; i++){
fileCnt = 0;
String[] str = br.readLine().split("/");
String lastName = "";
Folder nowFolder = null;
lastName = str[str.length-1];
for(int j=0; j<folderList.size(); j++) {
if (folderList.get(j).name.equals(lastName)) {
nowFolder = folderList.get(j);
HashSet<String> hs = new HashSet<>();
findFile(nowFolder, hs);
bw.write(hs.size() + " " + fileCnt + "\n");
}
}
}
bw.close();
}
static Folder findFolder(String P){
Folder ret = null;
for(int j=0; j<folderList.size(); j++){
if(folderList.get(j).name.equals(P)){
ret = folderList.get(j);
break;
}
}
return ret;
}
static void findFile(Folder folder, HashSet<String> hs) {
fileCnt += folder.childFile.size();
hs.addAll(folder.childFile);
if(folder.childFolder.size()!=0){
for(Folder f : folder.childFolder)
findFile(f, hs);
}
}
}
class Folder{
String name; //폴더 이름
List<Folder> childFolder = new ArrayList<>(); //하위폴더
List<String> childFile = new ArrayList<>(); //하위파일
Folder(String name){
this.name = name;
}
}Note
'BOJ' 카테고리의 다른 글
| [백준 20117번 / java] 호반우 상인의 이상한 품질 계산법 (0) | 2024.08.21 |
|---|---|
| [백준 14400번 / java] 편의점 2 (0) | 2024.08.21 |
| [백준 1082번 / java] 방 번호 (0) | 2024.08.19 |
| [백준 1477번 / java] 휴게소 세우기 (2) | 2024.08.01 |
| [백준 12904번 / java] A와 B (0) | 2024.07.31 |