BOJ13548 수열과 쿼리 6

문제

BOJ13548 수열과 쿼리 6
플래티넘I | 백준 13548 | Python3 파이썬 풀이

알고리즘

mo's 알고리즘은 업데이트가 없는 구간 쿼리 즉, 오프라인 쿼리를 처리하는 알고리즘이다.

mo's 알고리즘에 대해서는 이 블로그의 포스팅를 통해 공부하였다. (자세한 설명이 나와 있다)

간단하게 복습을 위해 설명해보자면,

두 개의 쿼리 Q1 = [s1, e1], Q2 = [s2, e2]가 있을 때, 두 개의 구간이 겹치는 경우

예를 들어, Q1 = [2, 6], Q2 = [5, 9] 일 때, 쿼리들의 순서를 잘 배치한다면 위 그림처럼 겹치는 구간인 [5, 6] 구간의 값을 다시 구하지 않고 재활용할 수 있다.

Q1 = [2, 8], Q2 = [4, 7] 일 때, Q2를 먼저 처리한 후, Q1을 처리한다면 Q2에 포함되는 것들은 미리 계산을 했으니, Q2에 포함된 원소를 제외하고, 나머지 원소들만 처리해도 Q1의 결과를 알아낼 수 있다.

이런 식으로 결과를 재사용한다면, Q1 = [s1, e1]의 결과를 재사용해서 Q2 = [s2, e2]의 결과를 구하는 시간은 O(|s2 - s1| + |e2 - e1|)이 된다. 이 값을 최소화하면 된다.

해법은 원소가 k = O(sqrt(N))개로 이루어진 버킷으로 나누고, 아래 조건 중 하나를 만족하는 경우, Q1을 Q2보다 먼저 처리하면 된다.

1. [s1 / k] < [s2 / k]
2. [s1 / k] = [s2 / k] & e1 < e2

위와 같은 알고리즘을 이용해 파이썬으로 코드를 작성해보았습니다.

자세한 알고리즘은 아래 코드에 주석으로 달아놓았습니다.

코드

import sys
from functools import cmp_to_key
from math import sqrt

input = sys.stdin.readline

# 쿼리를 정렬할 때, 사용되는 대소 비교 함수
def querysort(q1, q2):
    if q1[1] // sqrtN != q2[1] // sqrtN:
        # [s1 / k] < [s2 / k]
        if q1[1] // sqrtN < q2[1] // sqrtN:
            return 1
        else:
            return -1
    else:
        # [s1 / k] = [s2 / k] & e1 < e2
        if q1[2] < q2[2]:
            return 1
        else:
            return -1

    # 버킷 중 위의 두 가지 조건에 처리하는 것을 앞으로 정렬

# 카운트 증가
def Plus(x):
    global res
    if count[x] != 0:
        table[count[x]] -= 1
    count[x] += 1
    table[count[x]] += 1
    res = max(res, count[x])

# 카운트 감소
def Minus(x):
    global res
    table[count[x]] -= 1
    if count[x] == res and table[count[x]] == 0:
        res -= 1
    count[x] -= 1
    table[count[x]] += 1

N = int(input())
V = [0] + list(map(int, input().split()))
sqrtN = sqrt(N)


ans = [0] * 101010 

# count[x] : 구간에 존재하는 x의 개수
count = [0] * 101010 

# table[y] : count[x] == y를 만족하는 y 개수
table = [0] * 101010

# 최댓값
res = 0

query = []
Q = int(input())
for i in range(Q):
    S, E = map(int, input().split())
    query.append((i, S, E))

# 쿼리 정렬 (버킷)
# querysort 함수를 이용해 정렬한다
query = sorted(query, key=cmp_to_key(querysort))

s = 0
e = 0
res = 0

# 투 포인터를 이용해 쿼리 처리
for i in range(Q):
	# 쿼리의 start보다 작은 동안
    while s < query[i][1]:
    	# -> 이므로 빼주어야 한다
        Minus(V[s])
        s += 1
	
    # 쿼리의 start보다 큰 동안
    while s > query[i][1]:
    	# <- 이므로 더해주어야 한다
        s -= 1
        Plus(V[s])
	
    # 쿼리의 end보다 작은 동안
    while e < query[i][2]:
    	# -> 이므로 더해주어야 한다
        e += 1
        Plus(V[e])
	
    # 쿼리의 end보다 큰 동안
    while e > query[i][2]:
    	# <- 이므로 빼주어야 한다.
        Minus(V[e])
        e -= 1
	
    # 쿼리에 대한 결과 저장
    ans[query[i][0]] = res

for i in range(Q):
    print(ans[i])

결과

Python3는 시간초과가 발생하므로 Pypy3로 제출하였다.