알고리즘 스터디

www.acmicpc.net/problem/18870

18870번: 좌표 압축

정말 오랜만의 알고리즘이다...

간만에 들어와보니 단계별로 풀어보기에 문제가 추가됐다!

 

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

 

 

C++ 

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#define ll long long int

using namespace std;

int n;
int a[1000000];
int b[1000000];
int l;
int c;

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

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

  cin >> n;

  for (int i = 0; i < n; ++i){
    cin >> a[i];
    pq.push(make_pair(a[i], i));
  }

  auto t = pq.top();
  l = t.first;
  while(!pq.empty()){
    t = pq.top();
    pq.pop();
    if (t.first != l){
      l = t.first;
      ++c;
    }

    b[t.second] = c;
  }

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

  return 0;
}

 

어떻게 풀까 고민하다가 문득 떠오른 방법이 오름차순의 우선순위 큐를 만들어서 인덱스와 함께 저장하고

마지막으로 비교한 숫자를 l에 저장해서 비교하는 방법으로 해결했다.

c로 카운트를 +1 해가면서 풀었는데

분명 더 좋은, 메모리를 더 적게쓰는 방법이 있을 것 같은데 고민을 해봐야겠다.