[BOJ 18870] 좌표 압축(C++)

좌표 압축(Silver 2)

문제

전체 문제 보기

18870번: 좌표 압축

접근법

이번 문제는 sort 알고리즘을 두 번 적용하여 아래와 같이 해결할 수 있습니다.

• 입력받은 수 들을 오름 차순으로 정렬한다.
• 각 수들에게 0부터 순차적으로 순위를 매긴다. (크기가 같은 수는 같은 순위를 가집니다.)
• 다시 입력받은 순서대로 오름차순 정렬한다.
• 순서대로 순위를 출력한다.

자료구조 선택

각 수들은 순위와 입력받은 순서 데이터를 추가로 가져야 합니다. 따라서 다음과 같이 Data를 정의하고 Data를 원소로 가진 배열을 활용하여 문제를 풀수 있습니다.

struct Data {
    int num{};    // 입력받은 수
    int rank{}; // 해당 수의 순위
    int inputOrder{}; // 입력받은 순서
};

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
struct Data {
    int num{};
    int rank{};
    int inputOrder{};
};
// num 의 크기를 기준 오름차순 정렬할 비교 연산
bool compareNum(const Data& lhs, const Data& rhs)
{
    return lhs.num < rhs.num;
}
// 입력받은 순서로 오름차순 정렬할 비교 연산
bool compareInputOrder(const Data& lhs, const Data& rhs)
{
    return lhs.inputOrder < rhs.inputOrder;
}
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N; // 1 ≤ N ≤ 1,000,000
    cin >> N;

    vector<Data> nums(N);
    for (int i = 0; i < N; ++i)
    {
        int num;
        cin >> num;
        nums[i].num = num;
        nums[i].inputOrder = i;
    }

    // num을 기준으로 오름차순 정렬
    sort(nums.begin(), nums.end(), compareNum);
    int rank{};
    int prev = nums[0].num;

    // 각 수들의 순위를 매김
    for (int i = 1; i < N; ++i)
    {
        if (prev < nums[i].num) rank++;
        prev = nums[i].num;

        nums[i].rank = rank;
    }

    // 입력받은 순서대로 다시 오름차순 정렬
    sort(nums.begin(), nums.end(), compareInputOrder);

    // 각 수들의 순위 출력
    for (int i = 0; i < N; ++i)
    {
        cout << nums[i].rank << " ";
    }

    return 0;
}

 

다른 접근법

 

해당 문제는 unique 함수와 이분탐색 lower_bound 함수를 활용하여 아래와 같이 풀이할 수도 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N; // 1 ≤ N ≤ 1,000,000
    cin >> N;

    vector<int> nums(N);
    vector<int> orderedNums(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> nums[i];
        orderedNums[i] = nums[i];
    }

    sort(orderedNums.begin(), orderedNums.end());
    orderedNums.erase(unique(orderedNums.begin(), orderedNums.end()), orderedNums.end());

    for (int i = 0; i < N; ++i)
    {
        int answer = lower_bound(orderedNums.begin(), orderedNums.end(), nums[i]) - orderedNums.begin();
        cout << answer << " ";
    }

    return 0;
}