미니 빙고
면접 대비시간 제한1초메모리 제한512 MB
3x3 격자판과 시드 문자열이 주어질 때 점수 문자열을 구하고, 같은 점수 문자열을 만드는 시드 중 사전순으로 가장 앞선 것을 찾는다.
문제
Albert는 아래와 같은 3x3 격자판에서 하는 미니 빙고를 (mini BINGO) 즐겨한다. 이 문제를 풀기 위해 BINGO가 무슨 게임인지 알 필요는 없다.
Albert가 고안한 "미니 빙고" 놀이는 위와 같이 3x3 격자판에 서로 다른 영대문자 알파벳 9개를 적는 것으로 시작한다. 그리고 이 9개의 알파벳을 임의로 섞어서 길이 9인 문자열 를 하나 고르는데 이를 seed (시드) 문자열이라 부른다.
시드 문자열 S에 등장하는 알파벳 순서대로 격자판의 칸을 색칠하는데, 아래 조건에 따라 해당 칸의 점수를 매긴다.
- 방금 색칠한 칸이 속한 열 위에 놓인 3개의 칸 모두가 색칠됐다면 1점을 추가한다.
- 방금 색칠한 칸이 속한 행 위에 놓인 3개의 칸 모두가 색칠됐다면 1점을 추가한다.
- 방금 색칠한 칸이 주-대각선 (위 예제에서 A, F, K) 위에 있고 주-대각선 위의 3칸 모두 색칠 됐다면 1점을 추가한다.
- 방금 색칠한 칸이 반-대각선 (위 예제에서 C, F, I) 위에 있고 반-대각선 위의 3칸 모두 색칠 됐다면 1점을 추가한다.
이 방법을 통해 얻은 각 칸의 점수는 언제나 0이상 4이하이며, 이를 시드문자열과 같은 순서대로 적어 길이가 9인 문자열을 얻을 수 있다 - 이렇게 얻은 점수 문자열을 라 하자.
예를 들어 시드 문자열 = "JGFACKIEB" 인 경우를 살펴보자. 아래 그림에서 상단 1열부터 5열까지, 그리고 하단 1열부터 4열까지의 격자판은 시드 문자열에 따라 알맞은 칸을 순서대로 칠한 모습을 보여준다.
- 처음으로 칠해지는 다섯 개의 칸은 "
J", "G", "F", "A", "C"이며 각각 0점씩 점수를 부여한다. - 여섯 번째로 "
K"를 칠한 후 주-대각선과 3열 때문에 2점의 점수를 부여한다. - 일곱 번째로 "
I"를 칠한 후 3행과 반-대각선 때문에 2점의 점수를 부여한다. - 여덟 번째로 "
E"를 칠한 후 1열과 2행 때문에 2점의 점수를 부여한다. - 마지막으로 "
B"를 칠한 후 1행과 2열 때문에 2점의 점수를 부여한다. - 이리하여 최종적으로 얻게 되는 점수 문자열은 = "
000002222"가 된다.
같은 격자판에서 시드 문자열이 = "ABEGKCFIJ" 일 때, 아래와 같은 순서로 격자를 칠하고, 이때의 점수 문자열은 "000002222"가 된다.
위 예제에서 보이듯 서로 다른 시드 문자열의 점수 문자열이 같을 수 있다.
Albert는 임의의 격자판과 임의의 시드 문자열 가 있을 때 를 구하는 것이 너무 쉽다고 생각한다. 따라서 의 점수 문자열을 구한 후, 와 같은 점수 문자열을 () 만들어내는 모든 시드 문자열 중 사전순으로 가장 앞서는 시드 문자열을 찾고 싶다. Albert를 도와주자.
입력
입력 첫 줄에 테스트 케이스의 수 가 주어진다.
각 테스트 케이스의 첫 줄에는 길이 9인 시드 문자열 가 주어진다. 다음 세 줄에 걸쳐 3x3 격자판의 상태가 주어지는데 각 줄에 3개의 문자가 공백 없이 주어진다.
출력
각 테스트 케이스의 정답인 와 해당 점수 문자열을 얻게 하는 시드 문자열 중 사전순으로 가장 앞서는 문자열을 공백으로 구분하여 각 줄에 출력한다.
제한
- 시드문자열 는 길이가 9이며 알파벳인 '
A'-'Z' 만을 포함한다. 에 중복된 알파벳은 입력으로 주어지지 않는다. - 게임 격자판의 상태를 나타내는 총 9개의 알파벳은 시드 문자열 에 포함된 알파벳만 주어지며, 중복된 알파벳은 입력으로 주어지지 않는다.
힌트
문자열의 사전순 정의: 길이가 인 서로 다른 두 문자열 와 가 있을 때, 이 두 문자열이 처음 달라지는 위치가 번째라 하고 이 위치의 문자를 각각 , 라 했을 때, 와 의 사전식 순서는 두 알파벳 , 의 사전식 순서를 따른다.