h × w 크기의 행렬이 주어졌다고 가정해 보겠습니다. 행렬의 각 칸에는 영어 알파벳이 들어 있습니다. 우리가 만들어야 하는 것은 모든 행과 열이 회문(palindrome)인 새로운 행렬입니다. 즉, 어떤 방향에서 읽어도 앞뒤가 같은 형태가 되어야 합니다.
단, 행렬을 구성할 때 다음 두 가지 제약 조건이 있습니다.
- 주어진 행렬의 행과 열은 자유롭게 재배열할 수 있습니다.
- 하지만 개별 원소는 절대 변경할 수 없습니다. 예를 들어 'a'를 'b'로 바꾸는 것은 허용되지 않습니다.
이러한 조건 아래에서 회문 행렬을 만드는 것이 가능하면 true를, 불가능하면 false를 반환하면 됩니다.
예를 들어 h = 4, w = 4이고 mat = {"xxyy", "xyxx", "yxx y", "xyyy"}인 경우, 행과 열을 적절히 재배열하면 회문 행렬을 만들 수 있으므로 출력은 true(1)가 됩니다.
핵심 아이디어
회문의 성질을 생각해 보면, 길이가 L인 회문에서 각 문자는 대칭 위치에 짝을 이루어 배치됩니다. 이를 행렬 전체로 확장하면, 행 방향 대칭과 열 방향 대칭이 동시에 성립해야 하므로 한 문자가 완벽하게 배치되려면 그 등장 횟수가 4의 배수인 경우가 많습니다.
따라서 먼저 각 문자의 등장 횟수를 세고, 그 값을 4로 나눈 나머지(0, 1, 2, 3)별로 분류합니다. 나머지가 1 또는 3인 문자는 홀수 개가 남는 문자이고, 나머지가 2인 문자는 한 쌍이 남는 문자입니다. 행렬의 높이 h와 너비 w가 홀수인지 짝수인지에 따라 이런 '남는 문자'를 수용할 수 있는 정도가 달라지므로, 경우를 나누어 조건을 검사하는 것이 이 알고리즘의 핵심입니다.
알고리즘 단계
- 각 문자의 등장 횟수를 저장할 맵(map) tp를 정의합니다.
- 크기가 4인 배열 count를 선언합니다. count[k]는 '등장 횟수를 4로 나눈 나머지가 k인 서로 다른 문자의 개수'를 의미합니다.
- 행렬의 모든 칸을 순회하며 각 문자의 등장 횟수를 셉니다.
- 맵의 각 값 val에 대해 count[val % 4]를 1씩 증가시킵니다.
- check를 true로 초기화한 뒤, h와 w의 홀짝 여부에 따라 아래 조건을 검사합니다.
경우별 조건
- h와 w가 모두 짝수인 경우: 중앙에 홀수 개의 문자를 놓을 자리가 없으므로 모든 문자의 개수가 4의 배수여야 합니다. 따라서 count[1] + count[2] + count[3] > 0이면 check를 false로 설정합니다.
- h와 w가 모두 홀수인 경우: 전체 중앙 한 칸만 홀수 개의 문자를 수용할 수 있으므로, count[1] + count[3] > 1이면 불가능합니다. 또한 한 쌍씩 남는 문자의 종류 수(count[2])가 h/2 + w/2를 초과하면 역시 불가능하므로 check를 false로 설정합니다.
- 그 외(h, w 중 하나만 홀수인 경우): 홀수 개 남는 문자가 있으면 안 되므로 count[1] + count[3] > 0이면 불가능합니다. 추가로 h가 홀수일 때는 count[2] > w/2이면, w가 홀수일 때는 count[2] > h/2이면 불가능합니다.
모든 검사를 통과하면 check를 그대로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
bool solve(int h, int w, vector<string> mat){
map<char, int> tp;
vector<int> count(4);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j)
tp[mat[i][j]]++;
}
for (auto val : tp)
count[val.second % 4]++;
bool check = true;
if (h % 2 == 0 && w % 2 == 0) {
if (count[1] + count[2] + count[3] > 0)
check = false;
}
else if (h % 2 == 1 && w % 2 == 1) {
if (count[1] + count[3] > 1)
check = false;
else if (count[2] > h / 2 + w / 2)
check = false;
} else {
if (count[1] + count[3] > 0)
check = false;
else if (h % 2 == 1 && count[2] > w / 2)
check = false;
else if (w % 2 == 1 && count[2] > h / 2)
check = false;
}
return check;
}
int main() {
int h = 4, w = 4;
vector<string> mat = {"xxyy", "xyxx", "yxx y", "xyyy"};
cout << solve(h, w, mat);
return 0;
}
입력
4, 4, {"xxyy", "xyxx", "yxx y", "xyyy"}출력
1
출력값 1은 bool 타입의 true를 의미합니다. 즉, 주어진 행렬의 행과 열을 적절히 재배열하면 모든 행과 열이 회문이 되는 행렬을 만들 수 있다는 뜻입니다. 이 알고리즘은 문자 빈도수를 한 번만 세면 되므로 시간 복잡도는 O(h × w)로 매우 효율적입니다.