BOJ 백준 32277 스퀘어 게임
문제 : https://www.acmicpc.net/problem/32277
[ 문제 요약 ]
- 각 숫자들이 주어지고, 구간 쿼리가 주어집니다.
- 각 구간 안에서, 특정수들의 제곱을, 그 범위 안에 있는 숫자들의 합으로 만들 수 있다면 스퀘어라고 부릅니다. 제곱의 제곱도 만들 수 있으나 특정 수의 제곱을 만들 때 사용된 숫자들은 더 이상 사용할 수 없습니다. 이때, 스퀘어의 최대 횟수를 구합니다.
[ 테스트 케이스 설명 ]
1 // 테스트 케이스 개수(1<=32)
12 // 원소의 수(1<=50,000)
2 3 2 3 4 3 2 3 2 1 2 2 // 값 1<=1,000,000,000
3 // 쿼리 수(1<=50,000)
1 12
2 7
3 8
// 출력은 CASE #(테케번호)
Case #1
5
2
2
[ 알고리즘 분류 ]
- 오프라인 쿼리
- Mo’s 알고리즘
[ 문제 해설 ]
이 문제에서 주어지는 최대 원소 값이 10억인데, 계산해 보면 5만이 초과되는 숫자는 카운팅 할 필요 없습니다.
그 이유는, 5만의 제곱을 범위 안에서 구하려면 5만이라는 숫자가 5만 개 필요합니다. 그런데 문제에서 배열의 원소가 최대 5만 개이기 때문에 제곱으로 만들 수 있는 최대 수는 5만 개가 끝입니다.
숫자들의 등장 횟수를 카운팅 하면서, 특정 숫자가 나온 횟수가 그 특정 숫자와 같다면, 스퀘어가 가능합니다.
5*5는 25입니다. 그럼 5가 5개 있어야 25를 만들 수 있습니다. 모든 숫자가 이런 규칙을 따르기 때문에 특정 수의 나온 횟수가 특정수와 같다면 스퀘어가 가능한 것입니다.
이 특징을 통해 재귀를 이용해 간단하게 구현할 수 있습니다.( 코드에서 minus, plus 함수 참고 )
그리고 쿼리를 빠르게 처리하기 위해서 Mo’s 알고리즘으로 정렬 후 투 포인터로 이동해가면서 현재 범위 내에서 숫자들의 등장 횟수를 카운팅 합니다. 동시에 재귀 함수로 스퀘어를 추가, 삭제해줍니다.
Mo’s 알고리즘은 오프라인 쿼리로 처리 시 포인터의 이동을 최소화하기 위해 정렬할 때 사용합니다. 배열의 길이가 N이라면, 배열의 구간을 sqrt(N)으로 나눠 정렬하는 방법입니다.
이렇게 하면 연속한 두 쿼리 사이에서 포인터 L 과 R 이 한 번에 멀리 점프하는 일이 거의 사라져, 전체 이동 횟수가 O((N+Q)√ N)에 그치게 됩니다.
정렬된 쿼리를 순서대로 처리하면, [L, R] 범위 안에서 포인터를 몇 칸씩만 늘리거나 줄이게 되어 거의 상수 시간으로 배열을 탐색해 최빈도·합계·고유값 등 원하는 통계를 빠르게 구할 수 있습니다.
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
static final int MAX = 50_000;
static int count; // 스퀘어 횟수
static int cnt[]; // 각 숫자가 나온 횟수 카운팅할 배열 최대 5만까지
static int arr[]; // 입력된 초기 원소 들
static int ans[]; // 각 쿼리마다 결과를 담을 배열
static int N, Q;
static int sqrt; // Mo's 알고리즘을 위한 제곱근
static ArrayList<Query> query;
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());// 테스트 케이스 개수(1<=32)
for(int t=1; t<=T; t++)
{
N = Integer.parseInt(br.readLine());// 원소의 수(1<=50,000)
arr = new int[N + 1];
cnt = new int[MAX + 1];
sqrt = (int) Math.sqrt(N);
count = 0;
query = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)// 값 1<=1,000,000,000
arr[i] = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(br.readLine());// 쿼리 수(1<=50,000)
ans = new int[Q + 1];
for(int i=1; i<=Q; i++)
{
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
query.add(new Query(l, r, i, l / sqrt));
}
Collections.sort(query);
int L = 1;
int R = 0;
for(Query q : query)
{
while(R < q.right) plus(arr[++R]);
while(q.right < R) minus(arr[R--]);
while(L < q.left) minus(arr[L++]);
while(q.left < L) plus(arr[--L]);
ans[q.idx] = count;
}
sb.append("Case #").append(t).append('\n');
for(int i=1; i<=Q; i++)
sb.append(ans[i]).append('\n');
}
System.out.print(sb);
}
static void minus(int now) {
if(now > MAX || now == 1)// 범위 초과시 종료
return;
if(cnt[now] == 0) // 현재 줄여야하는데 줄일 값이 0이면 상위에서 줄여야 함
{
--count; // 스퀘어 횟수 -1 차감
cnt[now] = now; // 현재 값이 0이니, now로 원복
minus(now * now); // 상위로 넘어감
}
--cnt[now]; // 현재 카운트 감소
}
static void plus(int now) {
if(now > MAX || now == 1)
return;
++cnt[now];
if(cnt[now] == now)
{
++count;
cnt[now] = 0;
plus(now * now);
}
}
static class Query implements Comparable<Query>{
int left, right, idx, fac;
Query(int l, int r, int i, int f){
this.left = l;
this.right= r;
this.idx = i;
this.fac = f;
}
@Override
public int compareTo(Query o) {
// 구간이 다르면 구간 기준 오름차순 정렬
if(this.fac != o.fac)
return this.fac - o.fac;
// 구간의 값이 다르면, right기준 오름차순 정렬
return this.right - o.right;
}
}
}