[H1731] 이상한 나라의 알파벳

•  [제한 사항]

  
  

  시간	57개 테스트케이스를 합쳐서 C/C++의 경우 1초 / Java의 경우 2초 / Python의 경우 2초
  메모리	힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

  
  

  
  

  이상한 나라는 알파벳 순서가 이상하여 우리가 사용하는 a에서 z까지와는 다른 알파벳 순서를 사용한다.

  
  

  예를 들어서 부분적인 알파벳 순서가 luka 라고 하자.

  
  

  l이 u, k, a 보다 사전순으로 앞선 알파벳이며, u는 k, a보다 앞서고 k는 a보다 앞선 알파벳이다. 이에 따라 {uak, la, ualak, uka, ak, au} 를 사전 순으로 정렬하면, {la, uka, ualak, uak, au, ak} 가 된다.

  
  

  이번에 성삼대학교에 이상한 나라의 학생이 교환학생으로 왔다.

  
  

  당신과 팀워크를 하게 되었는데 당신은 이상한 나라의 알파벳 순서를 모른다.

  
  

  당신이 아는 유일한 사실은 사전 순으로 정렬되어 있는 이상한 나라의 단어들을 N개 뿐이다. 이를 이용해서 단어들에 사용된 알파벳들에 대해서 이상한 나라에서의 알파벳 순서를 구하는 프로그램을 작성하라.

  
  

  
  

  [입력]

  
  

  첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

  
  

  각 테스트 케이스의 첫 번째 줄에는 단어의 개수 N(1 ≤ N ≤ 100)이 주어진다. 이어서 개의 각 줄에 사전 순으로 정렬된 단어들이 주어진다. 각 단어들은 알파벳 소문자로 이루어져 있으며 길이는 모두 10이하이다.

  
  

  
  

  [출력]

  
  

  각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

  
  

  주어진 단어들에 사용된 알파벳들의 순서를 출력하라. 만약 그러한 순서가 존재하지 않으면 ‘!’을 출력하고 순서가 유일하지 않으면 ‘?’을 출력한다(작은 따옴표 제외하고 출력).

  
  

  
  

  입력 예제
  3 6 la uka ualak uak au ak 5 la uka ualak uak ak 6 cab cba abc acb bca bac	// 테스트 케이스 개수 // 첫 번째 테스트 케이스, N = 6             // 두 번째 테스트 케이스, N = 5

  
  

  출력 예제
  #1 luka #2 ? #3 !	// 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과

  #include <stdio.h> #define MAXN 105   struct queue {     int set[MAXN];     int sz = 0;     void POP() { sz--; }     void PUSH(int x) { set[sz++] = x; }     int TOP() { return set[sz - 1]; } };   int N; char word[MAXN][11];   int g[26][26]; int ind[26]; int main() {     int t; scanf("%d", &t); int tc = 1;     while (t--)     {         scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%s", word[i]);         for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) g[i][j] = 0;         for (int i = 0; i < 26; i++) ind[i] = -1;         for (int i = 0; i < N; i++) for (int j = 0; word[i][j]; j++) ind[word[i][j] - 'a'] = 0;           for (int i = 1; i < N; i++)         {             for (int j = 0; word[i - 1][j] && word[i][j]; j++)             {                 if (word[i - 1][j] == word[i][j]) continue;                 if (g[word[i - 1][j] - 'a'][word[i][j] - 'a'] == 0)                 {                     g[word[i - 1][j] - 'a'][word[i][j] - 'a'] = 1;                     ind[word[i][j] - 'a']++;                 }                 break;             }         }           char ans[30]; int cnt = 0; for (int i = 0; i < 30; i++) ans[i] = 0;         queue q;         for (int i = 0; i < 26; i++) if (ind[i] == 0) q.PUSH(i);           int type = 0;         while (q.sz)         {             if (q.sz >= 2) type = 1;             int x = q.TOP(); q.POP();             ans[cnt++] = x + 'a';               for (int i = 0; i < 26; i++)             {                 if (g[x][i])                 {                     g[x][i] = 0;                     --ind[i];                     if (ind[i] == 0) q.PUSH(i);                 }             }         }           for (int i = 0; i < 26; i++) if (ind[i] >= 1) type = 2;           if(type==0) printf("#%d %s\n", tc++, ans);         else if (type == 1) printf("#%d ?\n",tc++);         else printf("#%d !\n", tc++);     }     return 0; }