💡 값 / 좌표 압축/정렬
Memory 35468KB Time 1260ms Code Length 770B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int N;
unordered_map<int,bool> m;
vector<int> dict;
vector<int> target;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
if (m.find(num) == m.end()) {
m[num] = true;
dict.push_back(num);
}
target.push_back(num);
}
sort(dict.begin(), dict.end());
}
int find_target_index(int target_num) {
int st = 0;
int en = dict.size() - 1;
while (st <= en) {
int mid = (st + en) / 2;
if (dict[mid] < target_num) {
st = mid + 1;
}
else if (dict[mid] > target_num) {
en = mid - 1;
}
else {
return mid;
}
}
return 0;
}
int main() {
init();
for (int a : target) {
cout << find_target_index(a) << " ";
}
}
이 코드는 정수 N을 입력받고 N개의 정수를 입력받아 중복을 제거하고 정렬하는 과정을 거친다. 그 후 입력된 N개의 정수에 대해 중복이 제거된 정렬된 배열에서의 인덱스를 찾아 출력하는 프로그램이다.
추가적으로 수정해보기!
unordered 맵을 사용했을 때, 메모리가 무시무시하게 잡아먹는다. 그래서 수정을 해보았다.
Memory 9840KB Time 436ms Code Length 652B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<int> arr(N); // 원본 배열
vector<int> sorted(N); // 정렬될 배열
// 입력
for (int i = 0; i < N; i++) {
cin >> arr[i];
sorted[i] = arr[i];
}
// 정렬 및 중복 제거
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
// 각 원소마다 lower_bound로 위치 찾기
for (int i = 0; i < N; i++) {
cout << lower_bound(sorted.begin(), sorted.end(), arr[i]) - sorted.begin() << ' ';
}
return 0;
}
이 코드는 다음과 같이 동작한다:
- 먼저, 사용자로부터 정수 N을 입력받는다.
- 크기가 N인 두 개의 정수 벡터 arr과 sorted를 선언한다. arr은 사용자로부터 입력받은 값들을 저장하는 원본 배열이고, sorted는 arr을 정렬한 후 중복을 제거한 배열이다.
- 사용자로부터 N개의 정수를 입력받아 arr에 저장하고, 동시에 sorted에도 같은 값을 저장한다.
- sorted를 정렬하고 중복된 값들을 제거한다.
- 각 arr의 원소에 대해 sorted에서 lower_bound를 사용하여 그 원소의 위치를 찾은 후, 그 위치를 출력한다.
- 마지막으로 0을 반환하고 프로그램을 종료한다.
