DICTIONARY 해결좀 부탁드립니다..

  • junyoungwoo7
    junyoungwoo7

    동작은 다 맞게 돌아가는데 arrayList에 값이 항상 이상하게 들어가네요.... 예제 입력시 출력은
    INVALID HYPOTHESIS
    INVALID HYPOTHESIS
    zyxwvusrqpnmlkjhgfdeiotcba

    로 뜹니다 .. .ㅠㅠ 해결좀부탁드릴게요

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Scanner;

    public class DICTIONARY {
    static boolean[][] adj;
    static boolean[] visited;
    static List arrayList;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();
        for (int t = 0; t < testcase; t++) {
            int N = sc.nextInt();
            adj = new boolean[26][26];
            visited = new boolean[26];
    
            arrayList = new <Integer>ArrayList();
            String[] strArr = new String[N];
            for (int i = 0; i < N; i++) {
                strArr[i] = sc.next();
            }
            makeGraph(strArr);
            sort();
            if (!arrayList.isEmpty()) {
                for (int i = 0; i < arrayList.size(); i++)
                    System.out.print((char) (arrayList.get(i) + 'a'));
            }
            else
                System.out.print("INVALID HYPOTHESIS");
            System.out.println();
    
        }
    }
    
    public static void makeGraph(String[] strArr) {
        int len = 0;
        for (int j = 1; j < strArr.length; j++) {
            int i = j - 1;
            len = min(strArr[i].length(), strArr[j].length());
            for (int k = 0; k < len; k++) {
                if (strArr[i].charAt(k) != strArr[j].charAt(k)) {
                    int a = strArr[i].charAt(k) - 'a';
                    int b = strArr[j].charAt(k) - 'a';
                    adj[a][b] = true;
                    break;
                }
            }
        }
    }
    
    public static void dfs(int here) {
        visited[here] = true;
        for (int i = 0; i < visited.length; i++) {
            if (adj[here][i] == true && visited[i] == false) {
                dfs(i);
            }
        }
        arrayList.add(here);
    
    }
    
    public static void sort() {
        for (int i = 0; i < visited.length; i++)
            if (visited[i] == false)
                dfs(i);
        Collections.reverse(arrayList);
    
        for (int i = 0; i < adj[0].length-1; i++)
            for (int j = i + 1; j < adj[0].length; j++)
                if (adj[j][i] == true)
                    arrayList = new ArrayList();
    
    }
    
    public static int min(int a, int b) {
        return a > b ? b : a;
    }

    }


    2달 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.