[C++] 백준 25502번: 등차수열? 등비수열?

문제 링크

25502번: 등차수열? 등비수열?

문제 요약

수열이 주어지고, i번째 수를 x로 바꾸는 쿼리들이 주어진다. 각 쿼리를 수행할 때마다 해당 수열이 등차수열인지, 등비수열인지 또는 둘 다 아닌지 출력해야 한다.

접근 방법

매우 간단한 문제입니다.

N, M이 모두 최대 30만이기 때문에 나이브하게 매 쿼리마다 수열을 모두 검사하면 당연히 TLE를 받을 것입니다. 따라서, 수열 내에서 이웃한 수 사이의 차와 비만 카운트해주면 됩니다.

처음에 수열을 입력 받으면서, 차와 비를 모두 세어줍니다.

단, 문제에서 $A_i - A_{i - 1}$과 $A_i/A_{i-1}$이 모두 양의 정수여야 한다고 했기 때문에,

차 : $A_i>A_{i - 1}$인 경우
비 : $A_i \geq A_{i - 1}$이고 $A_i$ $mod$ $A_{i-1}$이 0인 경우

라는 조건을 충족해야 세어줍니다.

카운트는 std::map을 사용해주면 됩니다. <차, 갯수>, <비, 갯수> 쌍으로 각각 맵을 만들어줍니다.

쿼리를 수행하면서 i번째 수가 변경된다면, 변경되기 전의 현재 상태에서 차와 비를 계산해서 만약 조건에 부합한다면 해당 key에 대응되는 value를 1 감소해줍니다. 그리고 새로운 값을 기준으로 다시 차와 비를 계산해서 조건에 부합한다면 key에 대응되는 value를 1 증가시켜줍니다.

쿼리가 끝나고 이제 맵의 첫번째 원소의 value가 N - 1인지 확인해서 등차수열인지, 등비수열인지, 아무것도 아닌지 판별해주면 됩니다. 이때 이를 원활하게 하기 위해서는, 위에 value를 1 감소시킬 때, value가 0이 되면 맵에서 삭제해주는 것이 좋습니다.

코드가 생각보다 길어졌는데, std::map보다는 std::multiset을 사용하는 쪽이 메모리랑 시간은 더 먹어도 value가 0이 되면 맵에서 삭제하는 절차가 없어서 더 편했을 것 같습니다.

std::map이랑 std::unordered_map 둘 다 써서 제출을 해봤는데 결과는 동일하게 나왔던 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 300001;
long long arr[MAX];

bool check(long long num1, long long num2) {
    return num1 >= num2 && num1 % num2 == 0;
}

void increase(map<long long, int>& m, long long val) {
    m[val]++;
}

void decrease(map<long long, int>& m, long long val) {
    if(!--m[val]) {
        m.erase(val);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    map<long long, int> a, g;

    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        if(i >= 2) {
            if(arr[i] > arr[i - 1]) {
                increase(a, arr[i] - arr[i - 1]);
            }

            if(check(arr[i], arr[i - 1])) {
                increase(g, arr[i] / arr[i - 1]);
            }
        }
    }

    while(m--) {
        int i;
        long long x;
        cin >> i >> x;

        if(i > 1) {
            if(arr[i] > arr[i - 1]) {
                decrease(a, arr[i] - arr[i - 1]);
            }
            if(x > arr[i - 1]) {
                increase(a, x - arr[i - 1]);
            }
            if(check(arr[i], arr[i - 1])) {
                decrease(g, arr[i] / arr[i - 1]);
            }
            if(check(x, arr[i - 1])) {
                increase(g, x / arr[i - 1]);
            }
        }

        if(i < n) {
            if(arr[i + 1] > arr[i]) {
                decrease(a, arr[i + 1] - arr[i]);
            }
            if(arr[i + 1] > x) {
                increase(a, arr[i + 1] - x);
            }
            if(check(arr[i + 1], arr[i])) {
                decrease(g, arr[i + 1] / arr[i]);
            }
            if(check(arr[i + 1], x)) {
                increase(g, arr[i + 1] / x);
            }
        }

        arr[i] = x;

        if(!a.empty() && a.begin()->second == n - 1) {
            cout << "+\n";
        } else if(!g.empty() && g.begin()->second == n - 1) {
            cout << "*\n";
        } else {
            cout << "?\n";
        }
    }

    return 0;
}