[Leet Code] Find Duplicate File in System

안녕하세요!
오늘은 5월 3주차 4번째 알고리즘인 Find Duplicate File in System 풀이를 작성해보겠습니다.

---

문제

요약
주어지는 paths 에 directory 별 파일들과 해당 파일들에 포함되어있는 콘텐츠들이 적혀있습니다. 그 중 콘텐츠가 중복되는 파일의 경로를 return 하는 문제입니다.

처음 생각한 방법

문제를 딱 보자마다 HashMap 으로 풀어야겠다는 생각을 했습니다.

우선 문자열을 공백 기준으로 잘라서 가장 첫 문자열을 path 로 설정하고 그 다음 문자열부터 for문을 순회하면서 content를 key로 설정하고 나머지 file 명을 path 와 합쳐서 value 배열에 추가했습니다.
value 배열의 size가 2 이상이라면 중복된 파일들이므로 해당 배열을 answer 배열에 추가해서 return 해주었습니다.

코드 설명

HashMap<String, ArrayList<String>> fileMap = new HashMap<>();
List<List<String>> answer = new ArrayList<>();

content 와 파일들을 저장할 fileMap , 답변을 저장할 answer 변수를 선언해줍니다.

for (String path: paths) {
    String[] fileList = path.split(" ");
    String pathString = fileList[0];

    // ...
}

입력으로 주어지는 paths 를 순회하면서 문자열을 공백을 기준으로 split 합니다.
그리고 가장 처음에 주어지는 directory를 pathString 으로 저장합니다.

for (String path: paths) {
    // ...
    
    for (int i = 1; i < fileList.length; i++) {
        int splitIndex = fileList[i].indexOf("(");
        String content = fileList[i].substring(splitIndex + 1, fileList[i].length() - 1);
        String file = fileList[i].substring(0, splitIndex);

        if (!fileMap.containsKey(content)) {
            fileMap.put(content, new ArrayList<>());
        }
        fileMap.get(content).add(pathString + "/" + file);
    }
}

"(" 를 기준으로 문자열을 나눌 것이기 때문에 index 를 찾아줍니다.
content 부분은 (~~) 부분이므로 index+1 ~ length - 1 까지 범위를 잡아서 문자열을 추출합니다.
file 부분은 ~~( 부분이므로 0 ~ index 까지 범위를 잡아서 문자열을 추출합니다.

content를 key 로 설정하여 중복 검사를 해줄 것이기 때문에 추출한 content 가 fileMap 에 없다면 content 를 key로 하는 리스트를 넣어줍니다.
그리고 fileMap 에 content 와 file 의 디렉토리를 추가해줍니다.
file 의 디렉토리는 위에서 설정한 pathString 에 / 를 더하고 fileName 을 추가해주면 됩니다.

for (ArrayList<String> list: fileMap.values()) {
    if (list.size() >= 2) answer.add(list);
}

모두 fileMap 에 저장한 후에는 value 들을 추출해 for문을 순회하면서 리스트의 사이즈가 2 이상인 리스트들을 answer 에 더해줍니다.

전체 코드

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        HashMap<String, ArrayList<String>> fileMap = new HashMap<>();
        List<List<String>> answer = new ArrayList<>();

        for (String path: paths) {
            String[] fileList = path.split(" ");
            String pathString = fileList[0];

            for (int i = 1; i < fileList.length; i++) {
                int splitIndex = fileList[i].indexOf("(");
                String content = fileList[i].substring(splitIndex + 1, fileList[i].length() - 1);
                String file = fileList[i].substring(0, splitIndex);

                if (!fileMap.containsKey(content)) {
                    fileMap.put(content, new ArrayList<>());
                }
                fileMap.get(content).add(pathString + "/" + file);
            }
        }

        for (ArrayList<String> list: fileMap.values()) {
            if (list.size() >= 2) answer.add(list);
        }

        return answer;
    }
}

---

마무리

비교적 쉽게 풀려서 당황했던..? 문제였습니다.
처음에 딱 코드를 돌리자마자 Accept를 받은 것은 처음이네요..

이번 포스팅도 읽어주셔서 감사합니다 :)