[ 백준 18870] 좌표압축 (C++)

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

18870번: 좌표 압축

 

문제!

---

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

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

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

---

3줄밖에 안되는 문제가 너무 이해하기 힘든 문제였습니다..(제가 멍청해서..)

 

두번째 줄이 중요한데

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

이 말은 

2, 4, -10, 4, -9 가 존재 할때 

2보다 작은수의 갯수 >>> 2개

4보다 작은수의 갯수 >>> 3개

-10보다 작은수의 갯수 >>> 0개

-9 보다 작은수의 갯수 >>> 1개

 

이런식으로 압축을 하여

 

2, 3, 0, 3, 1로 만들어라! 하는 문제였습니다....

 

 

여기부턴 풀이 시작!

---

이해한 후 저의 첫번째 풀이는  >> 인덱스를 저장시킨 pair 벡터의 정렬이였습니다.

 

모든 좌표를 {현재값,인덱스} 로 저장해서 현재값기준으로 정렬후 count를 해주며 답을 구하겠다는 단순한 풀이!

 

숫자를 받고

 int n = 0;
    cin >> n;

    vector<pair<int, int>> num_list;
    vector<int> answer(n,0);

    int memo = 0;
    for (int i = 0; i < n; i++) {// 숫자받기
        cin >> memo;
        num_list.push_back({ memo,i });
    }

 

 

정렬시킨뒤 바로 좌표 압축결과를 answer에 넣어 주었습니다.

 sort(num_list.begin(), num_list.end()); // 정렬

    memo = num_list[0].first;
    int count = 0;


    for (int i = 0; i < n; i++) { 
        

        if (memo != num_list[i].first) {
            count += 1;
        }
        answer[num_list[i].second] = count;
        memo = num_list[i].first;
    }

 

풀이는 단순하지만 시간이.... 불안 불안 하네요...

 

 

여기서 아래의 코드를 추가해주면

   cin.tie(0);
    ios::sync_with_stdio(0);

 

 

바로 해결되네요 굳굳

 

 

**ALL

#include <iostream>
#include <vector>
#include <utility>

#include <algorithm>
using namespace std;

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

    int n = 0;
    cin >> n;

 ;
    vector<pair<int, int>> num_list;
    vector<int> answer(n,0);

    int memo = 0;
    for (int i = 0; i < n; i++) {// 숫자받기
        cin >> memo;
        num_list.push_back({ memo,i });
    }

    sort(num_list.begin(), num_list.end()); // 정렬

    memo = num_list[0].first;
    int count = 0;


    for (int i = 0; i < n; i++) { 
        

        if (memo != num_list[i].first) {
            count += 1;
        }
        answer[num_list[i].second] = count;
        memo = num_list[i].first;
    }
    //아래부터 0

    
    for (int i = 0; i < n; i++) {
        cout << answer[i] << " ";
    }




    return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!