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

 

12999번: 화려한 마을3

첫 번째 줄에 N, Q (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 수와 민호가 궁금해 하는 특정 구간의 수이다. 두 번째 줄에는 1번 집부터 N번 집까

www.acmicpc.net

구간 l ~ r에 존재하는 집에 칠해진 페인트의 밝기들 중 가장 많은 것의 갯수를 출력합니다.

즉, [l, r] 구간에 {1, 1, 1, 2, 2}가 있다면 1이 3개, 2가 2개이므로 3을 출력합니다.

 

이 문제에서 사용할 배열은

  • q: 쿼리 정보를 저장하는 배열
  • list: 페인트의 밝기를 저장하는 배열
  • ans: 답을 저장하는 배열
  • cnt: 특정 밝기의 등장 횟수
  • cntCnt: 특정 밝기의 등장 횟수의 등장 횟수

여기서 cntCnt는 1이 3번, 2가 3번 등장했다면 cntCnt[3] = 2 이렇게 되는 방식입니다.

페인트의 밝기는 -100000 ~ 100000이므로 100000을 미리 더해주도록 합시다. 그래서 cnt 배열의 크기는 *2가 됩니다.

 

페인트의 밝기는 업데이트가 되지 않으므로 오프라인 쿼리 사용이 가능합니다.

따라서 쿼리 정보를 한 번에 받아서 배열 q에 저장합니다.

출력은 입력 순으로 해야하니 인덱스도 함께 저장해야 합니다.

 

그 다음, 투 포인터 비슷하게 l ~ r 구간을 하나하나 확인하여 갯수 카운팅을 진행합니다.

하지만 범위가 1 ~ 5 -> 9 ~ 10 -> 1 ~ 2 이런식으로 된다면 포인터가 이동하는데 많은 시간이 걸릴 것입니다.

포인터를 효율적으로 이동시키기 위해 Mo's 알고리즘을 사용합니다.

Mo's 알고리즘으로 구간을 sqrt(N)으로 나누어서 최대한 같은 그룹 내에서 이동할 수 있도록 하여 움직임을 최소화할 수 있습니다.

따라서 l / sqrt(N)을 기준으로 오름차순으로 정렬하며, 같다면 r 기준으로 오름차순으로 정렬합니다.

 

이제 정렬된 쿼리를 하나씩 처리하면 됩니다.

구간을 이동시키면서 수를 제거하고, 추가합니다.

 

수를 제거하는 과정에서는 먼저 해당 수가 등장한 횟수인 cntCnt를 하나 빼야합니다.

1이 3번 등장해서 cntCnt[3] = 1이 되었는데, 구간을 이동시키니 1이 제거돼야 하는 상황이라면 1이 2번 등장하는 것으로 바뀌게 됩니다.

따라서 cntCnt[3]에서 1을 빼고, cntCnt[2]에서 1을 더해야 합니다.

이 때, 만약 cntCnt[3]이 0이 되었고, 그게 현재 최대 등장 횟수 ret이었다면 ret 또한 1을 빼야합니다.

 

수를 추가하는 과정에서는 해당 수가 처음 등장하는 수가 아니라면 cntCnt를 하나 빼줍니다.

1이 3번 등장해서 cntCnt[3] = 1이 되었고, 구간을 이동시켜서 1이 추가되는 상황이라면 1이 4번 등장하는 것으로 바뀌게 됩니다.

따라서 cntCnt[3]에서 1을 빼고, cntCnt[4]에서 1을 더해야 합니다.

물론, 1이 등장한 적 없다가 추가되는 상황이면 cntCnt를 빼지 않아야 합니다.

그리고 등장 횟수를 추가하는 과정이므로 최대 등장 횟수 ret을 계속 갱신합니다.

 

위 두 가지 작업이 완료되었다면 구간을 갱신하고, 쿼리의 인덱스에 맞게 정답을 넣어줍니다.

쿼리가 입력 순으로 정렬되어 있지 않으므로 출력은 마지막에 한꺼번에 진행합니다.

 

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

 

12986번: 화려한 마을2

첫 번째 줄에 N, Q (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 수와 민호가 궁금해 하는 특정 구간의 수이다. 두 번째 줄에는 1번 집부터 N번 집까

www.acmicpc.net

이 문제와 같은 풀이입니다.

하지만 화려한 마을2 문제는 다른 조건이 있어 다른 풀이로도 풀 수 있습니다.

저는 화려한 마을3을 먼저 풀었기에 같은 풀이로 AC를 받았습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAX 100001
using namespace std;
 
typedef struct Point {
    int l, r, idx;
}Point;
 
Point q[MAX];
int list[MAX], ans[MAX], cnt[MAX * 2], cntCnt[MAX];
int N, M, sqrtN;
 
bool cmp(Point a, Point b) {
    int x = a.l / sqrtN;
    int y = b.l / sqrtN;
    if (x == y) return a.r < b.r;
    else return x < y;
}
 
void func() {
    int l = q[1].l;
    int r = q[1].r;
    int ret = 0;
    for (int i = l; i <= r; i++) {
        int x = list[i] + 100000;
        if (cnt[x]) cntCnt[cnt[x]]--;
        cnt[x]++;
        cntCnt[cnt[x]]++;
        ret = max(ret, cnt[x]);
    }
    ans[q[1].idx] = ret;
 
    for (int i = 2; i <= M; i++) {
        int nl = q[i].l;
        int nr = q[i].r;
        int idx = q[i].idx;
 
        for (int j = l; j < nl; j++) {
            int x = list[j] + 100000;
            cntCnt[cnt[x]]--;
            if (!cntCnt[cnt[x]] && ret == cnt[x]) ret--;
            cnt[x]--;
            cntCnt[cnt[x]]++;
        }
        for (int j = l - 1; j >= nl; j--) {
            int x = list[j] + 100000;
            if (cnt[x]) cntCnt[cnt[x]]--;
            cnt[x]++;
            cntCnt[cnt[x]]++;
            ret = max(ret, cnt[x]);
        }
        for (int j = r; j > nr; j--) {
            int x = list[j] + 100000;
            cntCnt[cnt[x]]--;
            if (!cntCnt[cnt[x]] && ret == cnt[x]) ret--;
            cnt[x]--;
            cntCnt[cnt[x]]++;
        }
        for (int j = r + 1; j <= nr; j++) {
            int x = list[j] + 100000;
            if (cnt[x]) cntCnt[cnt[x]]--;
            cnt[x]++;
            cntCnt[cnt[x]]++;
            ret = max(ret, cnt[x]);
        }
 
        l = nl;
        r = nr;
        ans[idx] = ret;
    }
 
    for (int i = 1; i <= M; i++) {
        cout << ans[i] << '\n';
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    sqrtN = sqrt(N);
 
    for (int i = 1; i <= M; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].idx = i;
    }
    sort(q + 1, q + 1 + M, cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
cs

'algorithm > Mo's' 카테고리의 다른 글

boj 2912 백설공주와 난쟁이  (0) 2022.09.08

+ Recent posts