[Python] 2357번 최솟값과 최댓값 (추후 보강 예정)

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

---

 

24/03/15

 

 

대다수의 사람들이 해결한 방식인 세그먼트 트리로 해결하지 않고, 제곱근 분할법으로 해결한 문제이다.

 

세그먼트 트리로 해결한다면 이후 세그먼트 트리 풀이를 작성할 예정이다.

---

 

첫 번째 문제 접근 방식:

 

 

제곱근 분할법으로 해결했다.

 

제곱근 분할법은, 길이 $N$짜리 배열이 있다면 그 배열을 $\sqrt{N}$크기로 적당히 분할하여 시간 복잡도를 줄여보는 테크닉이다.

 

분할된 배열을 편의 상 버킷이라고 칭하겠다.

 

즉, 버킷의 크기는 $\lfloor \sqrt{N} \rfloor$이 되는 것이다.

 

그러면 $1$번 원소부터 $\lfloor \sqrt{N} \rfloor$번 원소까지 $1$번 버킷에 담기게 될 것이다.

그리고 $\lfloor \sqrt{N} \rfloor + 1$번 원소부터 $2 \lfloor \sqrt{N} \rfloor$번 원소까지 $2$번 버킷에 담기게 되고, 마찬가지로 $i$번 버킷에도 비슷하게 담기게 될 것이다.

 

우리는 각 버킷 별 최댓값과 최솟값만 버킷에 남길 것이다. 즉, $1$번 버킷에는 $1$번 원소부터 $\lfloor \sqrt{N} \rfloor$번 원소 중 최댓값과 최솟값만 남길 것이다.

 

이후, 처리해야하는 구간 $[l, r]$이 주어질 때, 버킷 별 최댓값과 최솟값을 적극 이용하여 시간을 줄일 것이다.

 

예를 들어, 구간 $[4, 100]$이 주어지고, 이 구간에는 $2$번 버킷과 $3$번 버킷, $4$번 버킷이 온전히 들어간다고 가정하자.

 

그러면 최댓값과 최솟값을 구할 때 굳이 $[4, 100]$구간을 모두 돌아볼 필요가 없다. $4$번 원소부터 $1$번 버킷 마지막 원소까지, 그리고 $2, 3, 4$번 버킷의 대푯값(최대, 최소), $5$번 버킷의 시작 원소부터 $100$번 원소까지만 돌아보면 충분하다.

 

하나의 쿼리를 처리하는 데에 드는 최악의 경우를 생각해 보자.

 

버킷의 크기가 대략 $\sqrt{N}$이므로, 버킷의 개수도 약 $\sqrt{N}$개 정도 된다.

 

최악의 경우는 시작 버킷과 마지막 버킷을 제외한 모든 버킷이 구간에 들어가고, $2$번째 원소부터 $\lfloor \sqrt{N} \rfloor$번째 원소가 구간에 들어가며, 마지막 버킷의 시작 원소부터 마지막 버킷의 마지막에서 두 번째 원소까지가 구간에 들어가는 경우이다.

 

이 경우, 우리는 대략 $3\sqrt{N}$번의 비교 연산을 수행해야 한다. 따라서 하나의 쿼리를 처리하는 데에는 최악의 경우 $\mathcal{O}(\sqrt{N})$의 시간 복잡도가 소요된다.

 

쿼리의 개수를 $Q$라고 할 때, 최종적으로 소요되는 시간 복잡도는 $\mathcal{O}(Q\sqrt{N})$이 된다.

 

나의 경우, 최댓값과 최솟값을 배열 두 개를 사용해 따로 관리하였다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 2357번 최솟값과 최댓값
# 제곱근 분할법
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [int(input()) for _ in range(N)]
bucket_size = int(N**.5)
min_bucket = [1_000_000_000 for _ in range(N//bucket_size + 1)]
max_bucket = [0 for _ in range(N//bucket_size + 1)]
# 초기화
for i in range(N):
    min_bucket[i//bucket_size] = min(min_bucket[i//bucket_size], A[i])
    max_bucket[i//bucket_size] = max(max_bucket[i//bucket_size], A[i])
def query(l, r):
    M, m = 0, 1_000_000_000
    left_bucket_num, right_bucket_num = l//bucket_size, r//bucket_size
    for i in range(left_bucket_num+1, right_bucket_num):
        M = max(M, max_bucket[i])
        m = min(m, min_bucket[i])
    if left_bucket_num == right_bucket_num:
        for i in range(l, r+1):
            M = max(M, A[i])
            m = min(m, A[i])
    else:
        for i in range(l, (left_bucket_num+1)*bucket_size):
            M = max(M, A[i])
            m = min(m, A[i])
        for i in range(right_bucket_num*bucket_size, r+1):
            M = max(M, A[i])
            m = min(m, A[i])
    return m, M
ans = []
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    print(*query(a, b))