[BOJ/백준] 25624 - SNUPTI

25624번: SNUPTI

---

각 척도의 결과에 사용되는 알파벳은 모두 서로 다르다.

 

+

 

마시로는 모든 문자열의 목록을 만들어서 카루나에게 전달하기로 했다

---

---

• 제목

SNUPTI 

---

• 조건

시간 제한 : 2 초

메모리 제한 : 1024 MB 

---

• 문제

마시로와 카루나는 MBTI에 대항할 새로운 심리검사 SNUPTI를 개발 중이다.

SNUPTI는 N개의 척도를 사용하며, i번째 척도의 결과는 Si개의 서로 다른 알파벳 대문자 중 하나로 나타낸다. (1 ≤ N ≤ 26, 1 ≤ i ≤ N, 1 ≤ Si ≤ 26) SNUPTI의 결과는 각 척도의 결과를 나타내는 알파벳을 순서대로 나열한 문자열로 나타낸다. 지표를 이해하기 쉽게 하기 위해서 각 척도의 결과에 사용되는 알파벳은 모두 서로 다르다.

마시로는 SNUPTI의 결과로 가능한 모든 문자열의 목록을 만들어서 카루나에게 전달하기로 했는데, 실수로 마시고 있던 달콤한 코코아를 흘려버려서 목록의 내용을 읽을 수 없게 되어버렸다. 결국 귀찮아진 마시로는 길이 N의 알파벳 대문자로만 이루어진 문자열 M개의 목록을 적당히 만들어서 카루나에게 전달했다. 게다가 각 척도에 대해 가능한 결과를 전달하지도 않아서, 카루나는 목록이 맞게 만들어졌는지 확인할 수가 없었다. 대신에 카루나는 문자열의 목록으로부터 각 척도의 가능한 결과를 거꾸로 만들어 내기로 했다.

카루나는 i번째 척도에 대해 가능한 결과를 나타내는 알파벳의 집합 Ai를 만들어서, 이로부터 가능한 지표의 검사결과 문자열만이 마시로가 전달한 목록에서 모두 각각 한 번씩만 등장하도록 하고 싶다. (1 ≤ i ≤ N) 이때 각 척도의 결과에 사용되는 알파벳은 모두 서로 달라야 한다. 즉, 1 ≤ i < j ≤ N에 대해 Ai ∩ Aj = ∅이어야 한다.

---

• 입력

첫째 줄에 SNUPTI에 사용되는 척도의 개수 N과 마시로가 카루나에게 전달한 문자열의 목록의 길이 M이 주어진다. (1 ≤ N ≤ 26; 1 ≤ M ≤ 20,000)

둘째 줄부터 M개의 줄에 마시로가 전달한 문자열의 목록이 한 줄에 문자열 하나씩 주어진다. 각 문자열은 길이 N의 알파벳 대문자로만 이루어진 문자열이다.

---

• 출력

카루나가 각 척도의 가능한 결과를 거꾸로 만들어 낼 수 있다면 첫째 줄에 YES를, 아니라면 NO를 출력한다.

카루나가 각 척도의 가능한 결과를 거꾸로 만들어 낼 수 있다면 둘째 줄부터 N개의 줄에 A1, A2, ⋯, AN에 대해 각 집합의 원소를 알파벳 순으로 나열해 이어붙인 문자열을 한 줄에 하나씩 출력한다.

---

예제 입력1	예제 출력1
4 16 ENTP ENFP INTP INFJ ESTJ INTJ ISFJ ESFP ESTP INFP ENTJ ISTP ESFJ ISFP ISTJ ENFJ	YES EI NS FT JP

예제 입력2	예제 출력2
2 6 AA AO BB BO OO AB	NO

예제 입력3	예제 출력3
2 4 AA AB BA BB	NO

예제 입력4	예제 출력4
2 4 AD BC AC BD	YES AB CD

예제 입력5	예제 출력5
2 3 AD BC AC	NO

예제 입력6	예제 출력6
2 5 AD BC AC BD BC	NO

예제 입력7	예제 출력7
4 7 BAKE CAKE FAKE LAKE MAKE TAKE WAKE	YES BCFLMTW A K E

---

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'

int main() {
    fastio;
    int alphabet[26], sz, tc;
    for(int n = 0 ; n < 26 ; n++) alphabet[n] = -1;
    priority_queue<char, vector<char>, greater<char>> order[26];
    map<string, bool> dict;
    string snupti;
    bool able = true;
    cin >> sz >> tc;
    for(int k = 0 ; k < tc ; k++){
        cin >> snupti;
        if(dict.find(snupti) != dict.end()) able = false;
        else dict.insert({snupti, true});
        if(!able) continue;
        for(int n = 0 ; n < sz ; n++){
            if(alphabet[snupti[n] - 'A'] == -1){
                alphabet[snupti[n] - 'A'] = n;
                order[n].push(snupti[n]);
            }
            else if(alphabet[snupti[n] - 'A'] != -1 && alphabet[snupti[n] - 'A'] != n) able = false;
        }
    }
    if(!able) cout << "NO" << endl;
    else{
        int sum = 1;
        for(int n = 0 ; n < sz ; n++) sum *= order[n].size();
        if(sum != tc) cout << "NO" << endl;
        else{
            cout << "YES" << endl;
            for(int n = 0 ; n < sz ; n++){
                while(!order[n].empty()){
                    cout << order[n].top();
                    order[n].pop();
                }
                cout << endl;
            }
        }
    }
    return 0;
}