[백준/13548] 수열과 쿼리 6 (Python)

Problem : https://www.acmicpc.net/problem/13548

13548번: 수열과 쿼리 6

 

Difficulty : Platinum 1

 

Status : Solved(pypy3)

 

Time : 00:36:00

 

---

 

문제 설명

 

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100,000)
셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.
넷째 줄부터 M개의 줄에는 쿼리 i, j가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ n)

 

출력

 

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

 

입력 예시

 

5
1 2 1 3 3
3
1 3
2 3
1 5

 

출력 예시

 

2
1
2

 

 

---

 

풀이

 

핵심 알고리즘은 이전 문제와 같다.

 

2023.12.17 - [알고리즘 문제/백준] - [백준/13547] 수열과 쿼리 5 (Python)

[백준/13547] 수열과 쿼리 5 (Python)

 

즉 오프라인 쿼리와 mo's로 구간 카운팅을 진행하면 되는데... 이제 그 카운팅한 최댓값을 출력하는 게 남았다. 

여기서 히스토그램에 힌트를 얻어, 등장하는 수를 추가적으로 카운팅하는 방식을 생각해 보자. 만약 i번째의 숫자가 nums[i]이고, 등장하는 수가 cnt[nums[i]]이고, 이를 구간에 포함시키고자 한다면

 

• 원래 등장하는 수 카운트가 table[cnt[nums[i]]] 라면, table[cnt[nums[i]]]는 1 감소할 것이다.
• 그리고 cnt[nums[i]] 값은 1 증가하게 되고,
• 업데이트된 수가 가리키는 카운트 table[cnt[nums[i]]]는 1 증가할 것이다.

 

구간에서 배제하는 경우 역시 비슷하게 업데이트된다. 또한, 이 카운팅 업데이트 과정 중 최댓값을 효과적으로 관리할 수 있으므로 상수 시간 내에 최빈값이 등장하는 카운트를 업데이트할 수 있겠다.

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = 100001
N = int(input())
sqrt = N ** 0.5
nums = list(map(int, input().split()))
M = int(input())
ans = [0]*M

queries = [[i] + list(map(int, input().split())) for i in range(M)]
queries.sort(key = lambda x : (x[1] // sqrt, x[2]))

num_list = [0]*MAX
cnt, prev_i, prev_j = 0, 0, -1
table = [0]*(N+2)
table[0] = N
for idx, i, j in queries :
  i -= 1
  j -= 1
  while prev_j < j :
    prev_j += 1
    table[num_list[nums[prev_j]]] -= 1
    num_list[nums[prev_j]] += 1
    table[num_list[nums[prev_j]]] += 1
    cnt = max(num_list[nums[prev_j]], cnt)
  while prev_j > j :
    table[num_list[nums[prev_j]]] -= 1
    if cnt == num_list[nums[prev_j]] and not table[cnt] :
      cnt -= 1
    num_list[nums[prev_j]] -= 1
    table[num_list[nums[prev_j]]] += 1
    prev_j -= 1
  while prev_i < i :
    table[num_list[nums[prev_i]]] -= 1
    if cnt == num_list[nums[prev_i]] and not table[cnt] :
      cnt -= 1
    num_list[nums[prev_i]] -= 1
    table[num_list[nums[prev_i]]] += 1
    prev_i += 1
  while prev_i > i :
    prev_i -= 1
    table[num_list[nums[prev_i]]] -= 1
    num_list[nums[prev_i]] += 1
    table[num_list[nums[prev_i]]] += 1
    cnt = max(num_list[nums[prev_i]], cnt)
  ans[idx] = cnt
print(*ans, sep = '\n')

풀이 완료!