[백준] 14725번. 개미굴(JAVA)

문제

https://www.acmicpc.net/problem/14725

---

풀이(30분)

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

public class Main {

    // 어차피 끝까지 내려가는 것은 보장되어있다.
    // 그럼 중요한 것은 깊이에 따른 사전순 배열이다.
    // 길이는 중요하지않고 사전순 배열이기만 하면 된다.
    // 또한 이걸 출력하는 것이 중요하다.

    static final String FLOOR_SEPARATOR = "--"; // 구분자

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        ArrayList<String[]> list = new ArrayList<>();

        int n = Integer.parseInt(br.readLine()); // 정보의 개수

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int count = Integer.parseInt(st.nextToken()); // 먹이의 개수
            
            String[] root = new String[count]; // 먹이의 개수만큼 배열 선언
            for(int j = 0; j < count; j++){
                root[j] = st.nextToken();
            }
            list.add(root); // 리스트에 추가
        }

        Collections.sort(list, ((o1, o2) -> { // 리스트 커스텀 정렬
            int minLength = Math.min(o1.length, o2.length);
            for(int i = 0; i < minLength; i++){
                if(!o1[i].equals(o2[i])){
                    return o1[i].compareTo(o2[i]); // 다른 부분이 발견됐다면 사전식 배열
                }
            }
            return o1.length - o2.length; // 모든 부분이 다 같다면, 길이가 더 긴 것이 뒤로
        }));

        StringBuilder sb = new StringBuilder(); // 정답 스트링빌더
        
        String[] first = list.get(0); // 첫 번째 디폴트로 추가
        for(int i = 0; i < first.length; i++){
            for(int j = 0; j < i; j++){
                sb.append(FLOOR_SEPARATOR);
            }
            sb.append(first[i]).append("\n");
        }

        StringBuilder separator; // 깊이에 따른 구분자 스트링빌더
        for(int i = 1; i < list.size(); i++){
            separator = new StringBuilder(); // 스트링 빌더 초기화
            String[] before = list.get(i-1); // 이전 것이랑 비교
            String[] cur = list.get(i); // 현재의 문자 배열
            int depth = depthCheck(before, cur); // 어디서부터 달라지는지 확인
            for(int j = 0; j < depth; j++){ // 달라지기 시작한 부분까지 디폴트 구분자 생성
                separator.append(FLOOR_SEPARATOR);
            }
            for(int j = depth; j < cur.length; j++){ // 달라진 만큼만 추가
                sb.append(separator); // 구분자 추가
                sb.append(cur[j]).append("\n"); // 문자 추가
                separator.append(FLOOR_SEPARATOR); // 구분자 확장
            }
        }

        System.out.println(sb);
    }

    /**
     * 몇 번째 깊이까지 같은지 확인
     * @param first 비교하고자 하는 앞의 문자열(사전순)
     * @param second 비교하고자 하는 뒤의 문자열(사전순)
     * @return 달라진 깊이
     */
    static int depthCheck(String[] first, String[] second){
        int minLength = Math.min(first.length, second.length);
        for(int i = 0; i < minLength; i++){
            if(!first[i].equals(second[i])){ // 문자가 달라졌다면
                return i; // 인덱스 반환
            }
        }
        return minLength; // 최소 길이까지 같다면 최소 길이가 다를 것임.
    }

}

---

문제 풀이 전략

 

문제를 분석해 보면 끝까지 개미굴을 타고 내려가는 것은 보장되어 있다.

즉, 사전순으로 정확하게 정렬한 뒤 이를 출력하는 것이 매우 중요한 문제이다.

 

먼저 입력된 값들을 정렬하기 위해 ArrayList<String[]> 자료구조를 사용한다.

이를 통해 list를 각 입력에 대한 깊이를 탐색하며 사전순으로 정렬할 수 있게 해주는 것이다.

Collections.sort(list, ((o1, o2) -> { // 리스트 커스텀 정렬
    int minLength = Math.min(o1.length, o2.length);
    for(int i = 0; i < minLength; i++){
        if(!o1[i].equals(o2[i])){
            return o1[i].compareTo(o2[i]); // 다른 부분이 발견됐다면 사전식 배열
        }
    }
    return o1.length - o2.length; // 모든 부분이 다 같다면, 길이가 더 긴 것이 뒤로
}));

 

위의 코드를 보면 리스트를 정렬할 때, 최소 길이를 먼저 설정한다.

최소 길이까지 각 배열의 인덱스를 비교해 가며 사전식 배열을 해준다.

만약 모든 분이 다 같다면, 길이가 더 긴 것을 뒤로해준다. -> 사실 이 부분은 문제 자체에서 보장되어 있다.

 

이후에는 출력을 해주면 된다.

이전 인덱스와 비교해 가며 깊이에 맞춰 "--" 구분자를 추가하고, 뒤에 문자를 붙이는 방식이다.