백준 18870 - 좌표 압축(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

좌표 압축 문제였습니다. 

문제 조건

출력 예시

unique를 통해 중복을 없앤뒤, lower_bound를 이용해 답을 출력한다.

저는 해당 방법으로 풀었습니다.

 

vector에서 unique를 통하면 중복되는 값을 없앨 수 있습니다. 

이때는 연속으로 중복되는 값을 지워주는 것이기에 정렬을 해준 뒤에 사용해줘야 합니다.

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

해당 코드를 사용하면 됩니다.

 

중복된 값을 없앴다면, lower_bound를 통해서 찾길 원하는 값이 어디있는지를 알아냅니다.

코드에서 lower_bound를 직접 구현해놨으니 익혀두시길 바랍니다.

 

문제 접근 방법

1. vector로 값을 받은 뒤, 해당 vector를 정렬한다.

2. vector속 중복되는 값들을 없애준다.

3. lower_bound를 이용해 원하는 값이 몇번째에 있는지를 확인한다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int N;
vector<int> X, Y;

int lower_bound(int x) {
	int low = 0;
	int high = X.size() - 1;
	int ret = 10000001;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (X[mid] >= x) {
			if (ret > mid) ret = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return ret;
}

void solve() {
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i = 0; i < Y.size(); i++) {
		cout << lower_bound(Y[i]) << " ";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x;
		cin >> x;
		X.push_back(x);
		Y.push_back(x);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요