백준 알고리즘 18870(좌표 압축) - python, c++

백준 알고리즘 18870(좌표 압축) - python, c++

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

18870번: 좌표 압축

주어진 입력에 대한 좌표를 압축하여 각 index에 맞는 rank를 mapping 해주는 문제.

문제는 간단하지만 구현은 은근히 까다롭다. (O(N^2)으로 구현했다가 시간 초과 당함)

---

[문제 해결 - python]

python은 short-coding을 목적으로 진행

1. 입력 _list를 받아서 set(중복 제거) 이후에 sort를 시킨다.

2. 속도는 역시 dictionary!

    - 중복 제거와 정렬이 된 set_list의 값을 key로 이용

    - value 값을 index로 mapping 시킨 result 생성

    - 배열에서의 index-value를 거꾸로 value-index 매칭시킨 효과

3. result 출력 시에 _list의 index 기준으로 출력

 

import sys
N = int(sys.stdin.readline())
_list = list(map(int, sys.stdin.readline().split()))
set_list = sorted(list(set(_list))) # 중복 제거, 정렬
# 속도는 dictionary! key-value mapping
result = {set_list[i]: i for i in range(len(set_list))}
for i in range(N):
    print(result[_list[i]], end=' ')

 

[문제 해결 - c++]

c++은 본질적인 구현을 목적으로 진행

rank는 mapping 시에 자신보다 작은 값의 갯수를 count하면 된다.

주의할 점은, 값이 같을 경우에는 rank의 count를 올리지 않는다는 점이다. 

 

1. 입력 vec에 값과 index를 부여에 입력

2. sort를 통하여 x[0] 기준 정렬(default가 x[0] 기준)

3. x[1](index) 기준으로 result에 mapping

    - mapping 시에 자신보다 작은 값의 갯수를 count하면 된다.

    - 이미 정렬되어있기 때문에 비교 시에 다른 값이면 큰 값이다.

    - vec에서 좌우를 비교하며 result를 채워간다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	scanf("%d", &N);
	vector<pair<int, int>> vec;
	int X_n = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &X_n);
		vec.push_back({X_n, i}); // X_n, index
	}
	sort(vec.begin(), vec.end());
	vector<int> result(N);
	int rank = 0; // 작은 갯수 count
	for (int i = 1; i < N; i++) {
		// sort 되어있기 때문에 다른 값이면 큰 수
		if (vec[i-1].first != vec[i].first) { // X_n 비교
			rank++;
		}
		result[vec[i].second] = rank;
	}
	for (int i = 0; i < N; i++) {
		printf("%d ", result[i]);
	}
	return 0;
}