단어 사각형(Word Square)이란?
단어 사각형은 여러 개의 단어를 정사각형 격자 형태로 배치한 것으로, 가로로 읽은 단어와 세로로 읽은 단어가 서로 동일하도록 구성된 배열을 말합니다.
예를 들어, 다음은 유효한 단어 사각형의 대표적인 예시입니다.
H E A R T
E M B E R
A B U S E
R E S I N
T R E N D
위 배열에서 첫 번째 행을 가로로 읽으면 'HEART'이고, 첫 번째 열을 세로로 읽어도 'HEART'입니다. 두 번째 행과 열 역시 모두 'EMBER'로 일치하며, 나머지 행과 열도 같은 방식으로 대칭을 이룹니다.
문제 정의
우리는 문자열 배열을 입력으로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 주어진 배열이 유효한 단어 사각형을 이루고 있다면 true, 그렇지 않다면 false를 반환해야 합니다.
예를 들어, 입력 배열이 다음과 같다면,
const arr = [
"abcd",
"bnrt",
"crmy",
"dtye"
];
출력 결과는 다음과 같아야 합니다.
const output = true;
이 배열에서 i번째 행의 j번째 문자와 j번째 행의 i번째 문자가 항상 동일하기 때문에 유효한 단어 사각형으로 판단됩니다.
구현 예제
핵심 아이디어는 간단합니다. 2차원 배열의 대칭성을 검사하는 것입니다. 즉, 모든 위치 (i, j)에 대해 arr[i][j]와 arr[j][i]가 같은지 확인하면 됩니다. 또한 배열 범위를 벗어나는 경우에는 즉시 false를 반환하여 비정형(정사각형이 아닌) 배열도 올바르게 처리할 수 있습니다.
코드는 다음과 같습니다.
const arr = [
"abcd",
"bnrt",
"crm",
"dt"
];
const findValidSquares = (arr = []) => {
for(let i = 0; i < arr.length; i++){
for(let j = 0; j < arr[i].length; j++){
// 행렬 범위를 벗어나면 유효하지 않음
if(i >= arr.length || j >= arr.length || j >= arr[i].length || i >= arr[j].length){
return false;
}
// 대칭 위치의 문자가 다르면 유효하지 않음
if(arr[i][j] !== arr[j][i]){
return false;
}
}
}
return true;
};
console.log(findValidSquares(arr));
코드 설명
- 이중 반복문: 바깥 반복문은 각 행(i)을 순회하고, 안쪽 반복문은 해당 행의 각 문자(j)를 순회합니다.
- 범위 검사:
i >= arr.length또는j >= arr[i].length등의 조건으로 현재 위치가 배열의 경계를 넘었는지 확인합니다. 이 덕분에 각 행의 길이가 달라도 문제없이 처리됩니다. - 대칭 검사:
arr[i][j] !== arr[j][i]조건을 통해 가로와 세로가 뒤바뀐 위치의 문자가 일치하는지 검사합니다. 하나라도 불일치하면 즉시false를 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
true
입력 배열의 각 행 길이가 다르더라도(4, 4, 3, 2) 대칭 조건만 만족한다면 유효한 단어 사각형으로 인식됩니다. 이 알고리즘의 시간 복잡도는 O(N × M)로, N은 행의 개수, M은 평균 행 길이입니다.