반응형
https://www.acmicpc.net/problem/2465
2465번: 줄 세우기
첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/51
[ 자료구조 ] 세그먼트 트리 (Segment Tree)
1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1
rudalsd.tistory.com
1. 키를 입력받고, map 자료구조를 활용해 각 키의 개수를 저장합니다.
2. 입력받은 키를 오름차순으로 정렬해 vector에 저장합니다.
3. vector의 인덱스를 기준으로 segment tree를 만듭니다.
4. 키의 순서를 N번째부터 1번째까지 돌면서 현재 남아있는 키 중에서 해당 정수 + 1만큼의 값을 가지고 있는 수를 ans 배열에 추가합니다.
5. ans 배열을 N번부터 1번까지 역으로 출력합니다.
[ 소스코드 ]
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include<iostream> #include<set> #include<unordered_map> #include<vector> using namespace std; int N; int segTree[262222]; unordered_map<int, int> m; set<int> se; vector<int> arr; vector<int> ans; int seq[100000]; void makeTree(int node, int s, int e) { if (s == e) { segTree[node] += m[arr[s]]; return; } int m = (s + e) / 2; makeTree(node * 2, s, m); makeTree(node * 2 + 1, m + 1, e); segTree[node] = segTree[node * 2] + segTree[node * 2 + 1]; } void updateTree(int node, int s, int e, int idx) { segTree[node]--; if (s == e) { ans.push_back(arr[s]); return; } int m = (s + e) / 2; if (segTree[node * 2] >= idx) { updateTree(node * 2, s, m, idx); } else { updateTree(node * 2 + 1, m + 1, e, idx - segTree[node * 2]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i < N; i++) { int n; cin >> n; se.insert(n); m[n]++; } arr.push_back(-1); for (auto& next : se) { arr.push_back(next); } makeTree(1, 1, arr.size() - 1); for (int i = 0; i < N; i++) { cin >> seq[i]; } for (int i = N - 1; i >= 0; i--) { updateTree(1, 1, arr.size() - 1, seq[i] + 1); } for (int i = ans.size() - 1; i >= 0; i--) { cout << ans[i] << '\n'; } } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 18114번 - 블랙 프라이데이 (C++) (0) | 2023.08.09 |
---|---|
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++) (0) | 2023.08.08 |
[ 백준 ] 5012번 - 불만 정렬 (C++) (0) | 2023.08.05 |
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++) (0) | 2023.08.04 |
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++) (0) | 2023.08.03 |