C++ / 백준 / 18870 / 좌표 압축

문제

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

18870번: 좌표 압축

문제풀이

해당 좌표 X보다 작은 좌표 X가 몇 개 있는지를 출력하는 문제이다.

중복된 X는 개수에 포함이 되지 않는 것 같다.

처음에는 단순하게 for문을 두 번 사용하여 풀고, 이분 탐색으로 풀어봤는데 이중 for문은 시간 초과가, 이분 탐색은 잘 되긴 했지만 시간을 더 줄이기 위해 upper_bound를 사용했다.

입력받는 좌표들을 저장하는 벡터를 2개 선언한다.

하나는 unique함수를 이용하여 중복 없는 X좌표가 저장되는 벡터, 하나는 답을 출력하기 위한 벡터이다.

upper_bound를 이용하기 때문에 X벡터를 정렬하여야 한다.

해당 인덱스에 해당하는 X좌표 값의 idx값 - 1을 해야 한다.

upper_bound는 (시작, 끝, 찾는 값)이라면 찾는 값이 몇 번째 인지 나타내 주는 함수이기 때문에 -1을 하여 이 수보다 작은 수가 몇 개 있는지를 구하는 것이다.

 

 

코드

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

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

	int N = 0;
	int idx = 0;
	cin >> N;
	vector<int>X(N, 0);
	vector<int>X2(N, 0);

	for (idx = 0; idx < N; ++idx) {
		cin >> X[idx];
		X2[idx] = X[idx];
	}
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	for (int idx = 0; idx < X2.size(); ++idx)
		cout << upper_bound(X.begin(), X.end(), X2[idx]) -
		(X.begin() + 1) << ' ';
}