백준 18870번 문제 c++ 풀이#

문제#

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자

입력#

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력#

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

제한#

$1 ≤ N ≤ 1,000,000$ $-109 ≤ Xi ≤ 109$

예제 입력 1#

입력:
5
2 4 -10 4 -9

출력:
2 3 0 3 1

예제 입력 2#

입력 :
6
1000 999 1000 999 1000 999

출력 :
1 0 1 0 1 0

아이디어#

1. 해시 테이블에 존재하는 숫자를 저장하고 배열에 들어온 숫자를 저장합니다.
2. 배열을 복사하고 복사한 배열을 오름차순으로 정렬합니다.
3. 이진탐색으로 정렬된 배열을 탐색한뒤 인덱스를 각 요소마다 출력합니다.

1차 시도#

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int N;
vector<int> arr;
vector<int> sortedArr;
set<int> exist;

int binarySearch(int left, int right, int target)
{
    if (sortedArr[left] == target) return left;
    if (sortedArr[right] == target) return right;

    int mid = (left + right) / 2;

    if (sortedArr[mid] >= target) return binarySearch(left, mid, target);

    return binarySearch(mid + 1, right, target);
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int x;
        cin >> x;
        if (!exist.contains(x))
        {
            sortedArr.push_back(x);

            exist.insert(x);
        }
        arr.push_back(x);
    }

    sort(sortedArr.begin(), sortedArr.end());

    for (int i = 0; i < arr.size(); ++i) cout << binarySearch(0, sortedArr.size() - 1, arr[i]) << " ";
}

결과

맞았습니다!!

깃헙 링크 : Link