[BOJ 25624] SNUPTI
View as PDF마시로와 카루나는 MBTI에 대항할 새로운 심리검사 SNUPTI를 개발 중이다.</p>
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)</p>
둘째 줄부터 M개의 줄에 마시로가 전달한 문자열의 목록이 한 줄에 문자열 하나씩 주어진다. 각 문자열은 길이 N의 알파벳 대문자로만 이루어진 문자열이다.
출력 형식
카루나가 각 척도의 가능한 결과를 거꾸로 만들어 낼 수 있다면 첫째 줄에 YES를, 아니라면 NO를 출력한다.</p>
카루나가 각 척도의 가능한 결과를 거꾸로 만들어 낼 수 있다면 둘째 줄부터 N개의 줄에 A1, A2, ⋯, AN에 대해 각 집합의 원소를 알파벳 순으로 나열해 이어붙인 문자열을 한 줄에 하나씩 출력한다.
예제 입력 1
4 16
ENTP
ENFP
INTP
INFJ
ESTJ
INTJ
ISFJ
ESFP
ESTP
INFP
ENTJ
ISTP
ESFJ
ISFP
ISTJ
ENFJ예제 출력 1
YES
EI
NS
FT
JP예제 입력 2
2 6
AA
AO
BB
BO
OO
AB예제 출력 2
NO예제 입력 3
2 4
AA
AB
BA
BB예제 출력 3
NO예제 입력 4
2 4
AD
BC
AC
BD예제 출력 4
YES
AB
CD예제 입력 5
2 3
AD
BC
AC예제 출력 5
NO예제 입력 6
2 5
AD
BC
AC
BD
BC예제 출력 6
NO예제 입력 7
4 7
BAKE
CAKE
FAKE
LAKE
MAKE
TAKE
WAKE예제 출력 7
YES
BCFLMTW
A
K
E
Comments