[알고스팟] 고대어사전 :: 늦깎이 IT

[알고스팟] 고대어사전 URL

1. 입력으로 주어지는 단어의 순서가 사전 순서로 배치되어 있다.

2. 각 단어들마다 비교를 통해 각 문자들간의 우선순위를 비교해주는 연산이 필요하다.

3. 예를 들어, acb와 abb가 입력되었을 경우 맨 앞자리 알파벳은 같으므로 패스하고 두 번째 자리인 c가 b보다

우선한다는 것을 표시해야한다.

4. 각 단어들간의 우선순위는 26 X 26 인접행렬로 표현해도되고 연결리스트로 표현해도된다.

5. a~z 까지의 알파벳을 순차적으로 탐색하되 연결되어 있는 알파벳이 있다면 다시 그 알파벳부터 DFS탐색을

시작한다.

6. 순서가 정해져있는 경우이므로, 위상정렬을 한다고 생각하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    static int C, N;
    static boolean isCycle;
    static boolean[] visited, finished;
    static Stack<Character> stack;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        C = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= C; t++) {
 
            N = Integer.parseInt(br.readLine());
 
            String[] strArr = new String[N];
            int[][] adj = new int[26][26];
            visited = new boolean[26];
            finished = new boolean[26];
 
            stack = new Stack<>();
            isCycle = false;
 
            for (int i = 0; i < N; i++)
                strArr[i] = br.readLine();
 
            makeAdjacent(adj, strArr);
 
            for (int i = 0; i < 26; i++) {
                if (!finished[i])
                    dfs(i, adj);
            }
 
            if (isCycle)
                System.out.print("INVALID HYPOTHESIS");
            else
                while (!stack.isEmpty())
                    System.out.print(stack.pop());
            System.out.println();
        }
    }
 
    public static void dfs(int v, int[][] adj) {
 
        visited[v] = true;
        for (int i = 0; i < 26; i++) {
 
            if (adj[v][i] == 1) {
 
                if (!visited[i])
                    dfs(i, adj);
 
                else if (!finished[i])
                    isCycle = true;
            }
        }
        finished[v] = true;
        stack.push((char) (v + 'a'));
    }
 
    public static void makeAdjacent(int[][] adj, String[] strArr) {
 
        int length = strArr.length;
 
        for (int i = 0; i < length - 1; i++) {
 
            int wordLen = Math.min(strArr[i].length(), strArr[i + 1].length());
 
            for (int j = 0; j < wordLen; j++) {
 
                if (strArr[i].charAt(j) != strArr[i + 1].charAt(j)) {
                    adj[strArr[i].charAt(j) - 'a'][strArr[i + 1].charAt(j) - 'a'] = 1;
                    break;
                }
            }
        }
 
    }
}