[백준] 22861 폴더 정리 (Large) java 풀이

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/22861

(1) 조건 분석 📊

1. 폴더 구조 형성 명령어
   • 맨 마지막에 1이 오면 폴더 간의 부모-자식 관계를 나타냄
   • 맨 마지막에 0이 오면 특정 폴더에 파일 삽입 명령어
2. 폴더 이동 명령어
   • 폴더 A, 폴더 B 구조로 알려주면 폴더 A를 B로 옮긴다.
3. 폴더 하위 파일 수 + 파일 유형 출력 명령어

2. 코드가 나오기까지 🛠️

KEY WORD: 시뮬레이션, 자료구조

먼저 개념을 나누고자 한다.

• 직속 파일: 해당 폴더에 존재하는 파일이다.
• 하위 파일: 해당 폴더의 하위 폴더 중 어딘가에 존재하는 파일이다.

(0) 폴더의 종류를 구분하는 이유

폴더 정리 (small)를 풀면서 직속파일과 하위파일을 구분없이 누적하여 풀었던 풀이자들은 해당 풀이를 고수할 경우 문제 풀이가 어려워진다. 왜냐하면 폴더 이동에 따라 누적 파일의 개수와 하위의 중복 없는 파일 유형의 동기화가 깨질 수 있기 때문이다.

문제에서 주어진 예시를 보면 초기 상태는 다음과 같을 것이다.

이후 folderB의 내용물을 folderA로 옮기면 다음과 같이 FIle 1이 덮어써지므로, 파일 유형은 그대로지만 파일 개수는 줄여야한다.

헌데 직속 파일과 하위 파일을 혼합해서 관리하고 있었다면, 이러한 파일 이동을 구현하기가 매우 어려워진다.

앞으로 합병하고 삭제될 폴더를 from 폴더, 합병해서 커질 폴더를 to 폴더라고 해보자. 합칠 때 중복된 파일 리스트를 만들고, to 폴더의 부모 폴더들에서 중복된 파일 유형에 관해서는 누적 파일 개수를 올리지 않는 방식의 풀이를 생각할 수 있지만

1. to, from 공통 부모일 경우 처리, 공통 부모가 아닌 경우 처리 구현 따로 짜야한다는 점
2. 매번 부모 폴더의 모든 폴더 유형을 검색해야 한다는 점

에서 복잡도가 오르고 성능이 낮아진다. (필자가 이렇게 풀었으나 시간초과가 낫다.)
따라서 누적합으로 관리하지말고, 폴더마다 직속 파일, 하위 파일들을 구분하여 관리하면 문제를 쉽게 풀 수 있다.

(1) 폴더 관리와 파일 이동

static class Folder {  
    HashSet<String> subFolders;  
    HashSet<String> subFiles; // 직속 파일만 저장  

    public Folder (){  
        subFolders = new HashSet<>();  
        subFiles = new HashSet<>();  
    }  
}

subFolder는 하위 폴더들의 이름, subFiles는 자신의 직속 파일들의 이름을 저장한다.
이후 폴더간의 합병이 있을 경우 from 폴더에 있는 모든 하위 폴더와 직속 파일들을 to 폴더로 쏟아버리면 된다. HashSet이기 때문에 중복 제거도 자동적으로 되고, 따로 부모와 자식 폴더를 잇는 과정도 불필요해진다.

하지만 주의해야할 점이 있는데, 다음과 같다.

(2) From 폴더의 부모 자식 관계 끊기

위의 예시에서 folderB의 내용물을 folderA로 쏟아넣은 뒤, folderB가 없어진 것을 볼 수 있다. 이것을 구현해야하는 이유는 이후 파일 이동 계산을 하려는데 folderB가 아직도 이전 부모 폴더에 붙어있다면 이후 계산이 어그러질 수 있기 때문이다.

지우려면 folderB의 부모 폴더를 알아야 하는데, 문제에서 파일 이동 명령어를 줄 때 경로 자체를 주므로 거기서 꺼내 쓰면된다.

(3) 특정 폴더가 가진 전체 폴더 개수 및 파일 유형 출력

• 전체 파일 유형 출력
  :재귀를 돌며 그것의 하위 폴더들의 파일을 모두 하나의 SET에 저장한다. -> 중복 제거
• 전체 폴더 개수
  : 재귀를 돌며 파일을 만날 때마다 전체 폴더 개수 +1 하면 된다.

(4) 시간복잡도 분석 ⏳

매 폴더 이동 명령어에서 파일의 최대치인 1,000개를 다 옮긴다고 해도 최대 $1,000 \times 1,000 = 1,000,000$ 개여서 해당 풀이로는 시간초과가 나지 않는다.

3. 코드 🌐

import java.io.*;  
import java.util.*;  

/*  
* 폴더 정리 (Large)* 1. 폴더와 파일 입력으로 unionfind 만들기 -> 경로 압축하지 말기  
* 2. 파일 입력 시 부모 노드 타고 가며 + 1씩 다 해주기  
*/  

public class Main {  
    static class Folder {  
        HashSet<String> subFolders;  
        HashSet<String> subFiles; // 직속 파일만 저장  

        public Folder (){  
            subFolders = new HashSet<>();  
            subFiles = new HashSet<>();  
        }  
    }    static int N,M,K,Q; // 폴더 수, 파일 수, 이동 명령어 수, 프린트 명령어  
    static String [][] relation_order;  
    static String [][][] move_order;  
    static String [] print_order;  
    static HashMap<String, Folder> tree = new HashMap<>();  
    public static void main(String[] args) throws IOException {  
        input();  
        for (String [] order : relation_order){  
            if(order[2].equals("1")) makeDir(order[0], order[1]);  
            else addFile(order[0], order[1]);  
        }  
        for (String [][] order : move_order){  
            moveFolder(order[0], order[1]);  
        }  
        StringBuilder answer = new StringBuilder();  
        HashSet<String> all_types = new HashSet<>();  
        int [] sum = new int[1];  
        for(String order : print_order){  
            all_types.clear();  
            sum[0] = 0;  
            calculate(order, sum, all_types);  
            answer.append(all_types.size()).append(" ").append(sum[0]).append("\n");  
        }  
        System.out.println(answer);  
    }  

    public static void makeDir(String parent, String child){  
        tree.compute(parent, (k,ov)-> ov == null? new Folder() : ov);  
        tree.compute(child, (k,ov) -> ov == null? new Folder() : ov);  
        tree.get(parent).subFolders.add(child);  
    }  

    public static void addFile(String folder, String file){  
        tree.get(folder).subFiles.add(file);  
    }  

    public static void moveFolder(String [] fromPaths, String [] toPaths){  
        Folder from = tree.get(fromPaths[fromPaths.length-1]);  
        Folder to = tree.get(toPaths[toPaths.length-1]);  
        // from 폴더 자체를 원래 경로에서 지우기  
        tree.get(fromPaths[fromPaths.length-2]).subFolders.remove(fromPaths[fromPaths.length-1]);  
        // from 폴더의 폴더들과 파일들을 to 폴더에 쏟기  
        to.subFolders.addAll(from.subFolders);  
        to.subFiles.addAll(from.subFiles);  
        // from 폴더 비우기  
        from.subFolders.clear();  
        from.subFiles.clear();  
    }  

    public static void calculate(String folder, int [] sum, HashSet<String> set){  
        Folder now = tree.get(folder);  
        sum[0] += now.subFiles.size();  
        set.addAll(now.subFiles);  
        for (String sub : now.subFolders){  
            calculate(sub, sum, set);  
        }  
    }  

    public static void input() throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());  
        M = Integer.parseInt(st.nextToken());  
        relation_order = new String[N+M][3];  
        for(int i = 0; i < N+M; i++){  
            relation_order[i] = br.readLine().split(" ");  
        }  
        Arrays.sort(relation_order, (row1, row2) -> Integer.parseInt(row2[2]) - Integer.parseInt(row1[2]));  
        K = Integer.parseInt(br.readLine());  
        move_order = new String[K][2][N+1];  
        for (int i = 0; i < K; i++) {  
            st = new StringTokenizer(br.readLine());  
            String [] to = st.nextToken().split("/");  
            String [] from = st.nextToken().split("/");  
            move_order[i][0] = to;  
            move_order[i][1] = from;  
        }  
        Q = Integer.parseInt(br.readLine());  
        print_order = new String[Q];  
        for (int i = 0; i < Q; i++) {  
            String [] path = br.readLine().split("/");  
            print_order[i] = path[path.length-1];  
        }  
    }}

4. 트러블 슈팅 or 배운 점📝

(1) 풀이 방식 오판

필자는 출력 명령 부분에서 해당 폴더의 모든 하위 폴더를 순회하며 파일을 일일히 세는 과정이 시간 초과가 날 것이라 판단했다. 그래서 매번 폴더 이동 시, 덮어쓰기 된 파일을 따로 관리하며 부모 폴더에서 해당 파일은 따로 누적 파일 개수에 영향이 가지 않도록 풀었다.

하지만 이 중복 리스트 관리 풀이가 오히려 시간초과가 났다. 필자가 분석한 이유는 모든 부모 트리마다 중복리스트 전체와 부모 폴더의 누적 폴더 개수 전체를 비교해야해서 였다. 이렇게 되면 최악의 경우, 폴더 이동 한 번당 모든 폴더의 모든 누적 파일을 모두 순회해야 하므로 $1,000 \times 1,000 \times 1,000 = 10^9$ 가 되어 시간 초과가 될 것이다.

(2) Integer는 불변 객체

 StringBuilder answer = new StringBuilder();  
        HashSet<String> all_types = new HashSet<>();  
        int [] sum = new int[1];  
        for(String order : print_order){  
            all_types.clear();  
            sum[0] = 0;  
            calculate(order, sum, all_types);  
            answer.append(all_types.size()).append(" ").append(sum[0]).append("\n");  
        }  
        System.out.println(answer);  

해당 부분은 현재 출력명령어에 해당하는 폴더의 모든 하위 파일 개수와 유형을 세는 코드 부분인데, 파일 개수를 누적하는 sum을 int [] 배열로 넘기는 것을 볼 수 있다. 이는 배열의 주소값이 계산 함수의 인수로 넘겨지는 것을 활용해 함수가 끝나고도 값을 유지하도록 하기 위함이었다.

처음에는 해당 int [] sum 을 Integer sum으로 풀었지만 sum의 상태가 유지되지 않았다. 이유는 Integer는 불변 객체이기 때문이다. 불변 객체란 한 번 값이 정해지면 바뀌지 않는 객체를 뜻한다. 따라서 calculate(Integer sum)을 넘기면 sum의 주소값이 전달되는 것이 아니라 새로운 Integer 객체가 인수로 전달된다고 한다.

(3) ConcurrentModificationException

HashSet을 순회하면서 안의 내용을 삭제하려다가 위와 같은 오류가 났다. Collections 클래스를 상속받은 자료구조들 (ex - HashMap, HashSet, ArrayList 등)을 이터레이터로 순회하면서 그 안의 값을 해당 클래스 전용 remove() 로 삭제하려고 하면 위와 같은 오류가 난다.

그 이유는 Iterator로 순회를 할 때, iterator.next()를 사용하는데, 이 함수는 항상 modCount라는 int 값이 초기값과 달라졌는지 검사한다. 만약 초기값과 동일하지 않다면, 순회 중에 수정이 발생한 것이고, 이는 일관성을 유지할 수 없기에 오류를 낸다.
(collections 클래스의 안에 있는 modCount는 collections에서 삽입, 수정 삭제가 생길 때마다 증가하는 값이다.)

ArrayList는 내부가 배열로 이루어져 있기 때문에 for(int i = 0; …)으로 시작하는 단순 for문으로 돌면서 안의 값들을 수정할 수 있으나, 무조건 Iterator를 활용해서 순회해야 하는 set, map 유형들은 위의 오류가 발생한다.

[!info] 강화 for 문
for (Itneger now : hashSet) {} 형태로 된 강화 for 문도 내부적으로 iterator를 사용한다ㅏ.

A. 해당 오류를 피하면서 순회 중 remove를 하는 방법

각 자료구조 내부 remove 말고, Iterator 의 remove 매서드가 따로 존재하는데 이걸 사용해야 한다.
해당 삭제함수는 내부적으로 expectedModeCount 라는 값이 존재하는데, 이를 활용해 컬랙션 자료구조의 modCount를 삭제가 끝내고 매 번 동기화한다. 따라서 ConcurrentModificationException이 따로 생기지 않는다.

Iterator가 인터페이스라 그것을 구현한 방법은 자료구조마다 다르지만, ArrayList를 예로 들어보면 Iterator를 다음과 같이 구현하고 있다ㅏ.

private class Itr implements Iterator<E> {
    int cursor;       // 다음 반환할 요소의 인덱스
    int lastRet = -1; // 마지막 반환한 요소의 인덱스
    int expectedModCount = modCount; // ←← 여기 있다!

    public boolean hasNext() {
        return cursor != size;
    }

    public E next() {
        checkForComodification();  // expectedModCount 비교
        // ... 나머지 구현
    }
}

만약 iterator.remove()를 통해 현재 인덱스의 값을 삭제했으면, 구현체 내부적으로 마지막 사용 인덱스 (lastRet)을 통해 다음 next() 호출 시 방문해야할 인덱스를 계산하여 cursor를 옮긴다. 따라서 일관성 문제 없이 삭제를 진행할 수 있다.

5. 부록

A. 모르는 단어 정리

• play along with ~~
  : (상대방이 원하는 대로) 맞춰 주다. 동조해주다. 협조하다.
  (Fail-fast iterators in Java don't play along when the underlying collection gets modified.)
  (자바의 빠른 실패 이터레이터는 그것이 돌아가고 있는 컬렉션이 수정되었을 때 순순히 협조해주지 않는다.)

• abort
  : 중단하다.
  (Fail-Fast systems abort operation as-fast-as-possible exposing failures immediately and stopping the whole operation.)
  빠른 실패 시스템은 실패에 노출되는 즉시 작동을 중단한다. 그리고 모든 작동을 중단한다.

• basis
  : 기준, 방식, 방법
  (These iterators throw ConcurrentModificationException on a best effort basis.)
  (이터레이터는 최선을 다해 노력해서 동시수정 오류를 일으킨다.)

• favor A over B
  : A를 B보다 선호하다.
  (Faile-Safe Iterator favor lack of failure over the inconvenience of exception handling)
  (실패-안전 이터레이터는 예외 핸들링의 불편보다 실패가 없는 것을 더 선호한다.)

B. 참고 문서

• 벨둥 - fail-fast vs fail-safe

C. 관련 글