[백준] 18870번 좌표 압축

문제: 18870번: 좌표 압축

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int arr[1000005]; // 넉넉하게 잡아..
int sortedArr[1000005]; // 여기에 정렬되고, 중복 제거한 배열로 갱신

int maxIdx(int target, int len) {
    int st = 0;
    int en = len;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (sortedArr[mid] >= target) {
            en = mid - 1;
        }
        else {
            st = mid + 1;
        }
    }
    return en; // 마지막 en 의 값이 target 보다 작은 요소 중 제일 큰 값의 인덱스임
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        order[i] = num;
        arr[i] = num;
    }
    // arr 정렬
    sort(arr, arr + n);

    int idx = 0;
    sortedArr[idx++] = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i-1] != arr[i]) {
            sortedArr[idx++] = arr[i];
        }
    }

    for (int i = 0; i < n; i++) {
        int num = order[i];

        // num 의 Xnum' 값 구해여
        cout << maxIdx(num, idx) + 1 << " ";
    }
    
    return 0;
}

 

그냥 입력 받은 거 오름차순으로 정렬한 다음에 중복되는 값 제거한다. 제거한 후의 배열을 이분 탐색 돌려서 xNum 값을 구해주면 된다.

 

maxIdx 는 target 보다 작은 수 중 가장 큰 값의 인덱스를 가리키도록 했다.