[백준/C++] 18870번: 좌표 압축(S2)

문제

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

사용한 알고리즘

2022.01.11 - [PS/Algorithm] - [알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기

-> 비교함수 정의하기

 

풀이

1. idx, X, X'을 변수로 가지는 구조체 Point와 구조체 배열 생성
2. idx에 인덱스 입력, X를 입력받음
3. X를 기준으로 오름차순 정렬
4. 나의 왼쪽에 있는 원소중에 나보다 크기가 작은 원소의 개수를 변수X'에 저장
5. idx를 기준으로 오름차순 정렬
6. X'출력

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
//비교함수 정의

// 1. idx, X, X'을 변수로 가지는 구조체 Point와 구조체 배열 생성
struct Point{
    int idx; //인덱스
    int x; //입력(X)
    int y; //출력(X')
}p[1000001];

bool cmp1(const Point &a, const Point &b){
    return a.x<b.x;
}
bool cmp2(Point &a, Point &b){
    return a.idx<b.idx;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin>>n;
    
    // 2. idx에 인덱스 입력, X를 입력받음
    for(int i=0; i<n; i++){
        p[i].idx=i;
        cin>>p[i].x;
    }
    
    // 3. X를 기준으로 오름차순 정렬
    sort(p,p+n,cmp1); 
    
    // 4. 나의 왼쪽에 있는 원소중에 나보다 크기가 작은 원소의 개수를 변수X'에 저장
    p[0].y=0;
    for(int i=1,j=0; i<n; i++){
        if(p[i].x>p[i-1].x) j++;
        p[i].y=j;
    }
    
    // 5. idx를 기준으로 오름차순 정렬
    sort(p,p+n,cmp2);
    
    // 6. X'출력
    for(int i=0; i<n; i++){
        cout<<p[i].y<<" ";
    }
    return 0;
}