[BOJ] 13548 수열과 쿼리 6

PS/BOJ 2020. 9. 7. 23:10

13548번: 수열과 쿼리 6

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

www.acmicpc.net

알고리즘: Mo's

시간복잡도: $O((N+M)\sqrt N)$

모스 알고리즘을 배우면서 풀어본 문제이다.

모스 알고리즘을 이용하면 데이터를 추가 및 삭제를 하는데 $O(1)$ 만에 해결할 수 있고,

포인터 이동(?)을 하는데 최대 $(N+M)\sqrt N$이므로 제한 시간 내 해답을 구할 수 있다.

답을 구하는데 필요한 배열은 총 2개이다.

1. $cnt[x]:$ $A_i=x$의 개수

2. $map[x]:$ $cnt[]=x$의 개수

데이터를 추가, 삭제를 할 때 두 배열을 갱신해주면서 답을 구해주면 된다.

코딩 코딩