18870번 좌표 압축

문제링크 : 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을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2 

1 0 1 0 1 0

---

<알고리즘>

  1) 입력받은 배열을 복사한 후 오름차순으로 배열

  2) 동일한 값을 체크하지 않으므로 중복요소 제거

  3) 처음 입력받은 배열을 돌며 복사한 배열에서 해당 순서 값이 몇번째 값인지 찾아 index 출력하기

 

 

 

1차시도. 입력을 복사, 정렬, 동일요소 삭제 후, 인덱스 찾기 => 시간초과

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

int main() {
	int N = 0;
	cin >> N;

	vector<long long> num(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	vector<long long> tempNum(N, 0);
	tempNum = num;
	sort(tempNum.begin(), tempNum.end());
	tempNum.erase(unique(tempNum.begin(), tempNum.end()), tempNum.end());

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < tempNum.size(); j++) {
			if (tempNum[j] == num[i]) {
				cout << j << " ";
			}
		}
	}

	return 0;
}

 

 

2차시도.  find함수를 이용해 index를 찾는 시간을 줄여봄 => 시간초과

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

int main() {
	int N = 0;
	cin >> N;

	vector<long long> num(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	vector<long long> tempNum(N, 0);
	tempNum = num;
	sort(tempNum.begin(), tempNum.end());
	tempNum.erase(unique(tempNum.begin(), tempNum.end()), tempNum.end());

	for (int i = 0; i < N; i++) {
		cout << find(tempNum.begin(), tempNum.end(), num[i]) - tempNum.begin() << " ";
	}

	return 0;
}

 

 

정답. lower_bound 함수 이용 => 메모리 : 17648KB     시간 : 1060ms

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

int main() {
	int N = 0;
	cin >> N;

	vector<long long> num(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}

	vector<long long> tempNum(N, 0);
	tempNum = num;
	sort(tempNum.begin(), tempNum.end());
	tempNum.erase(unique(tempNum.begin(), tempNum.end()), tempNum.end());

	for (int i = 0; i < N; i++) {
		cout << lower_bound(tempNum.begin(), tempNum.end(), num[i]) - tempNum.begin() << " ";
	}

	return 0;
}

 

 

 

 

+) 추가 정보

 

sort 함수 

• <algorith> 헤더파일에 포함
• sort(begin, end)를 이용해 [begin,end) 범위의 요소들을 오름차순(default 값)으로 정렬하는 함수
• quick sort기반 함수라서 평균 시간 복잡도는 nlogn 이다.
• sort(v.begin(), v.end(), greater<자료형>()) //내림차순 sort(v.begin(), v.end(), less<자료형>()) //오름차순

 

unique 함수

• <algorithm> 헤더파일에 포함
• unique(begin, end)를 이용해 [begin,end) 범위의 요소들의 중복을 뒤로 빼는 함수
• 배열에서 중복되지 않는 원소들을 앞에서부터 채워나간다 => 중복된 부분들은 뒷부분에 남아있음
• unique(v.begin(), v.end())

 

erase 함수

• <algorithm> 헤더파일에 포함
• erase(begin, end)를 이용해 [begin, end)범위의 요소 인자를 삭제
• v.erase(v.begin(),v.end())

+) 위의 코드에서 erase함수는 unique 함수로 쓰레기값이 된 (뒤로 밀린)중복요소들을 삭제하는 역할

 

 

 

lower_bound 함수

• <algorithm> 헤더파일에 포함
• 탐색을 진행할 배열/벡터가 오름차순 정렬이 되어 있어야 한다.
• lower_bound(begin,end,target)을 이용해 [begin,end)범위에서 target요소가 가장 처음으로나오는 위치 반환
• 인덱스 번호가 알고 싶다면, 'lower_bound의 return값 - 해당 벡터의 begin값' 을 통해 알수 있다.
• int target = 0; lower_bound(v.begin(), v.end(), target); lower_bound(v.begin(), v.end(), target) - v.begin();