[18870번][실2] 좌표압축

푸는 방법은 아는데, 그 방법에 쓸 실행시간이 빠른 함수를 몰라서 틀린 문제. 이번에 알게된 함수를 정리해두자.

 

 

lower_bound (ary.begin(), ary.end(), ary에서 찾으려는 값) // 첫번째,두번째 인자에는 적용할 범위를 넣는다

• 찾으려는 값 이상의 숫자가 배열의 몇 번째에 처음 등장하는지 찾음.
• 사용할 배열은 오름차순으로 정렬되어 있어야 함.
• vector 배열에서 특정 값의 인덱스를 알고싶다면, (배열이 정렬돼 있을 때) lower_bound함수를 사용하는게 find를 사용하는 것보다 빠르다. (lower_bound를 find로 바꿔서 실행하면 시간 초과됨🥺)

 

 

unique(ary.begin(), ary.end()) // 인자에는 적용할 범위를 넣는다

• unique() 는 앞 뒤 원소를 비교하며 작동하기 때문에 반드시 정렬을 한 뒤 실행해야 함.
• 중복된 값은 사라지지 않고 배열의 맨 뒤에 붙는다. (1,1,2,2,3,4 -> 1,2,3,4,1,2 이렇게 바뀜)

 

coordAry.erase(ary.begin(), ary.end())  // 인자에는 적용할 범위를 넣는다

• 1번인자 이상,2번인자 미만의 범위를 모두 지운다

 

unique와 erase를 합쳐서 응용하면 

coordAry.erase(unique(ary.begin(), ary.end()), ary.end());

이렇게 중복값이 없는 배열을 만들 수 있다.

 

 

내 코드

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main() {
	vector<int> inputAry;
	vector<int> coordAry;
	vector<int>::iterator iter;
	int totalSize;
	int coord;

	cin >> totalSize;

	for (int i = 0; i < totalSize; i++) {
		cin >> coord;
		inputAry.push_back(coord);
		coordAry.push_back(coord);
	}

	sort(coordAry.begin(), coordAry.end());
	coordAry.erase(unique(coordAry.begin(), coordAry.end()), coordAry.end());//중복없는 배열 만듦

	/*출력*/
	for (int i = 0; i < inputAry.size(); i++) {
		iter = lower_bound(coordAry.begin(), coordAry.end(), inputAry[i]);//inputAry[i]의 인덱스 찾기.
		cout << iter - coordAry.begin() << " ";
	}

	return 0;
}

 

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축