고대어 사전 풀이

• 문제(알고스팟): https://algospot.com/judge/problem/read/DICTIONARY
• 제한시간: 1초

문제에서 주의할 점

• 최악의 case
  • 테스트 케이스: 50
  • 단어의 수: 1000
  • 단어의 길이 20
    • 1000개가 모두 20번째(단어마지막 길이까지) 비교해야 하면. 1000 * 20 = 20000 (2만)
    • 2만짜기 케이스 50 개면 100만 루프
  • 위 100만 루프 + 순서탐색 루프 해서 1억 이하면 될듯.
• 아이디어
  • 주어진 단어 비교시, <현재단어, 뒤에단어> 페어 형태로 만 비교 가능
  • 페어로 비교시, 하나의 문자(char)만 의미를 가짐 (앞, 뒤) 의미를 가짐
    • 따라서, 페어 비교시, 길이가 작은 단어 (len)까지만 비교하면됨
  • 영어 알파벳 순서를 만드는 문제
    • a-z 로 영어 알파벳 수는 고정
    • 전체 a-z 중, 문제에서 주어지는 단어(word)에서 알 수 있는 정보만 순서를 정해주면됨.
    • 문제 자체에 모순이면 에러 출력하게 되어있음.
• 문제에서 주의점
  • 에러(모순)(사이클): "INVALID HYPOTHESIS" 출력
  • 가능한 순서가 여러개면 아무거나 출력해도 됨
    • 즉 주어진 단어에서 얻을 수 있는 영어 알파의 순서는 무관벳의 순서만 맞으면 나머지 알파벳

순서가 있고, 순환(사이클) 이 없어야 하고, 해당 순서를 나열 하는 문제

따라서, 위상정렬로 풀이 가능, 사실 위상정렬로 풀수 있다는걸 떠올리는게 어려운 문제.

풀이코드

Java로 풀이함

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

class AlphabetSort {
    static final String INVALID_STR = "INVALID HYPOTHESIS";
    ArrayList<String> words;
    int graph[][] = new int[26][26];
    int visited[] = new int[26];
    int indegree[] = new int[26];
    LinkedList<Integer> tSortDFSList = new LinkedList<Integer>();

    public AlphabetSort(ArrayList<String> words) {
        super();
        this.words = words;
    }

    public boolean initGraph() {
        for (int w = 0; w < words.size(); w++) {
            if (w + 1 == this.words.size()) {
                break;
            }

            String cWord = this.words.get(w);
            String nWord = this.words.get(w + 1);

            int minLen = Math.min(cWord.length(), nWord.length());

            for (int cmpIndex = 0; cmpIndex < minLen; cmpIndex++) {
                char cChar = cWord.charAt(cmpIndex);
                char nChar = nWord.charAt(cmpIndex);

                // invalid check
                if (graph[nChar - 'a'][cChar - 'a'] == 1) {
                    return false;
                }

                if (cChar != nChar) {
                    graph[cChar - 'a'][nChar - 'a'] = 1;
             break;
                }
            }
        }

        return true;
    }

    public void dfs(int node) {
        int len = graph[node].length;
        visited[node] = 1;

        for (int i = 0; i < len; i++) {
            if (graph[node][i] == 1 && visited[i] == 0) {
                dfs(i);
            }
        }

        // save topological sort
        tSortDFSList.add(0, node);
    }
    public void topologicalSortDFS() {
        for (int i = 0; i < graph.length; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
    }

    public String getDictionary() {
        // init graph
        if (!initGraph()) {
            return INVALID_STR;
        }

        // topological sorting
        topologicalSortDFS();

        // toString
        String result = "";
        for (Iterator<Integer> it = tSortDFSList.iterator(); it.hasNext();) {
            char alpabet = (char) (it.next() + 'a');
            result += alpabet;
        }

        return result;
    }
}


public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < testCase; tc++) {
            int wordNumber = Integer.parseInt(br.readLine());

            ArrayList<String> words = new ArrayList<String>(wordNumber);
            for (int w = 0; w < wordNumber; w++) {
                words.add(br.readLine());
            }

            AlphabetSort al = new AlphabetSort(words);
            bw.write(al.getDictionary());
            bw.newLine();
        }

        br.close();
        bw.flush();
        bw.close();

    }
}