문제 설명
양의 정수로 이루어진 배열 A가 있다고 가정해 봅시다. 만약 배열 내 모든 인접한 원소 쌍의 합이 완전제곱수(perfect square)라면, 이 배열을 '스퀘어풀(Squareful) 배열'이라고 부릅니다. 우리가 구해야 하는 것은 배열 A의 순열 중에서 스퀘어풀 조건을 만족하는 순열의 개수입니다. 단, 두 순열 A1과 A2는 어떤 인덱스 i에서 A1[i]와 A2[i]의 값이 서로 다른 경우에만 다른 순열로 간주됩니다.
예를 들어 입력이 [3, 30, 6]이라면 출력은 2가 됩니다. [3, 6, 30]과 [30, 6, 3], 이 두 가지 순열만 조건을 충족하기 때문입니다.
알고리즘 접근 방법
이 문제는 백트래킹(Backtracking) 기법으로 효율적으로 해결할 수 있습니다. 각 자리에 원소를 하나씩 배치하되, 직전 원소와의 합이 완전제곱수가 되는 경우에만 탐색을 이어갑니다. 또한 같은 값이 동일한 단계에서 중복 선택되어 동일한 순열이 여러 번 세어지는 것을 막기 위해 방문 집합(visited set)을 활용합니다.
구체적인 해결 절차는 다음과 같습니다.
isSqr() 함수 정의 — 수 n을 매개변수로 받습니다.
x := n의 제곱근
(x * x)가 n과 같으면 true를 반환합니다.
solve() 함수 정의 — 배열 a와 현재 인덱스 idx를 매개변수로 받습니다.
idx가 배열 a의 크기와 같다면 count를 1 증가시키고 함수를 종료합니다.
중복 선택을 방지하기 위한 집합 visited를 선언합니다.
i를 idx부터 배열 끝까지 1씩 증가시키며 반복합니다.
(idx가 0이거나 isSqr(a[idx - 1] + a[i])가 참)이고, a[i]가 visited에 없다면 다음을 수행합니다.
a[idx]와 a[i]를 교환(swap)합니다.
solve(a, idx + 1)을 재귀 호출합니다.
a[idx]와 a[i]를 다시 교환하여 원상 복구합니다.
a[i]를 visited에 삽입합니다.
메인 함수에서는 다음을 수행합니다.
count := 0으로 초기화합니다.
solve(a, 0)을 호출합니다.
count를 반환합니다.
아래 예시 구현을 통해 더 자세히 이해해 보겠습니다.
예시 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int count;
bool isSqr(lli n){
lli x = sqrt(n);
return x * x == n;
}
void solve(vector<int>& a, int idx){
if (idx == a.size()) {
count++;
return;
}
set<int> visited;
for (int i = idx; i < a.size(); i++) {
if ((idx == 0 || isSqr(a[idx - 1] + a[i])) &&
!visited.count(a[i])) {
swap(a[idx], a[i]);
solve(a, idx + 1);
swap(a[idx], a[i]);
visited.insert(a[i]);
}
}
}
int numSquarefulPerms(vector<int>& a){
count = 0;
solve(a, 0);
return count;
}
};
int main(){
Solution ob;
vector<int> v = {3,30,6};
cout << (ob.numSquarefulPerms(v));
return 0;
}
입력
{3,30,6}출력
2
복잡도 분석
이 알고리즘은 최악의 경우 모든 순열을 탐색해야 하므로 시간 복잡도는 O(N!)에 가깝습니다. 하지만 완전제곱수 조건 검사와 중복 제거 덕분에 실제 탐색 공간은 크게 줄어들며, N이 작은 입력(대략 12 이하)에서는 충분히 빠르게 동작합니다.