BOJ 10975 : 데크 소트 2

• 문제 링크 : boj.kr/10975
• 난이도 : G5
• 태그 : 그리디, 정렬, 맵

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321
#define int long long

using namespace std;

using ld = long double;
using pii = pair<int,int>;

template <typename T1, typename T2>
istream& operator>>(istream & ist, pair<T1,T2> &p) {
    ist >> p.first >> p.second;
    return ist;
}
template <typename T>
istream& operator>>(istream & ist, vector<T> &arr) {
    for(auto &u : arr) ist >> u;
    return ist;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n);
    cin >> arr;

    vector<int> sa(all(arr));
    sort(all(sa));

    map<int, int> _m;
    for(int i = 0; i < n; i++) {
        _m[sa[i]] = i;
    }

    int ans = 0;
    vector<pii> deq_arr;
    for(int i = 0; i < n; i++) {
        int ni = _m[arr[i]];
        bool inserted = false;
        for(auto &u : deq_arr) {
            if(u.first - ni == 1) {
                u.first = ni;
                inserted = true;
                break;
            }
            else if(ni - u.second == 1) {
                u.second = ni;
                inserted = true;
                break;
            }
        }
        if(!inserted) {
            deq_arr.push_back({ni,ni});
        }
    }
    cout << deq_arr.size();
    return 0;
}

---

풀이

한 덱에 들어간 원소들의 정렬했을 때의 인덱스는 1씩 차이가 나야 한다.

따라서  어떤 덱에도 인덱스가 1씩 차이나도록 넣을 수 없다면 새로운 덱을 만들어서 넣어주어야 한다.

정렬했을 때의  인덱스를 구하기 위해 맵을 사용한다.