๋ฌธ์
์์ง์ ์์ 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
ํ์ด
์ผ๋จ ์ขํ ์์ถ์ด ๋ญ์ง๋ถํฐ ์์์ผ ํ๋ค.
๐ ์ขํ ์์ถ
์ ๋ ฅ๋ฐ์ ์ขํ๊ฐ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ์ ๋์ ์์ ํ์(์ค๋ณต์ ์ ์ธ)
์ฆ, ํด๋น ๊ฐ๋ณด๋ค ์์ ๊ฐ๋ค์ ๊ฐ์์ด๋ค!
์ด ๋ฌธ์ ๋ ์๊ฐ์ด ๊ต์ฅํ ๋นก๋นกํด์ ์ธ ๊ฐ์ง ๋ฐฉ๋ฒ์ผ๋ก ์๋ํด๋ดค๋ค.
01. ์ ์(algorithm - unique / lower_bound ์ฌ์ฉ)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(false);
int n;
cin >> n;
vector<int> v(n); // ์๋ณธ
// ์
๋ ฅ
while(n--){
cin >> v[i];
}
vector<int> v2(v); // ์ ๋ ฌ ๋ฐ ์ค๋ณต ์ ๊ฑฐ๋ฅผ ์ํํ ๋ฒกํฐ(์๋ณธ ๋ณต์ฌ)
sort(v2.begin(), v2.end()); //์ค๋ฆ์ฐจ์
v2.erase(unique(v2.begin(), v2.end()), v2.end()); // ์ค๋ณต ์ ๊ฑฐ
for (int i = 0; i < v.size(); i++){
// i๋ฒ์งธ ์์๊ฐ์ ์์น it
auto it = lower_bound(v2.begin(), v2.end(), v[i]);
cout << it - v2.begin() << ' ';
}
}
lower bound ํจ์ ์ค๋ช ์ ์ฌ๊ธฐ ์ฐธ๊ณ
https://chanhuiseok.github.io/posts/algo-55/
02. map์ ํ์ฉํ ํ์ด 1(์ฑ๊ณต์ ํ์ผ๋ ์์ฌ์์ฌํ ํ์ด)
int main(){
int n, x;
cin >> n;
map<int, int> rank; // key : ์ซ์, value : ์ขํ ์์ถ๊ฐ
vector<int> num, tmp;
while(n--){
cin >> x;
num.push_back(x);
}
tmp = num;
sort(tmp.begin(), tmp.end());
int idx = 1;
for (int i=0; i<tmp.size(); i++) {
if (!rank[tmp[i]])
rank[tmp[i]] = idx++;
}
for (int i=0; i<num.size(); i++){
cout << rank[num[i]] - 1 << " ";;
}
}
03. map์ ํ์ฉํ ํ์ด 2(์๊ฐ ์ด๊ณผ)
int main(){
ios::sync_with_stdio(false);
cin.tie(false);
int n, x;
cin >> n;
map<int, int> rank; // key : ์ซ์, value : ์ขํ ์์ถ๊ฐ
vector<int> num;
while(n--){
cin >> x;
rank[x]; // map์ key ๋ฃ์ด์ค(์๋ ์ ๋ ฌ)
num.push_back(x);
}
int i=0; // ์ขํ ์์ถ๊ฐ
for (auto & iter : rank) { // & ๋ถ์ฌ์ค์ผ ํจ
iter.second = i++; // ์์ถ๊ฐ ํ๋์ฉ ์ฆ๊ฐ
}
for (int i=0; i<num.size(); i++){
cout << rank[num[i]] << " ";;
}
}
'โจ Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/C++] 1620๋ฒ : ๋๋์ผ ํฌ์ผ๋ชฌ ๋ง์คํฐ ์ด๋ค์ (0) | 2021.09.12 |
---|---|
[๋ฐฑ์ค/C++] 14425๋ฒ : ๋ฌธ์์ด ์งํฉ (0) | 2021.09.12 |
[๋ฐฑ์ค/C++] 9375๋ฒ : ํจ์ ์ ์ ํ๋น (0) | 2021.09.12 |
[๋ฐฑ์ค/C++] 4358๋ฒ : ์ํํ (0) | 2021.09.12 |
[๋ฐฑ์ค/C++] 2015๋ฒ : ์๋ค์ ํฉ 4 (0) | 2021.09.12 |
๋๊ธ