반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 자료구조
- class_template
- template
- connected_component
- Articulation_Point
- Pair
- 13305
- Algorithm
- c++
- Heap
- red-black tree
- 문법
- Critical_Path_Analysis
- data_structure
- list
- '0'
- Biconnected_Component
- 총정리
- STL
- deletion
- singly Linked List
- qsort
- 알고리즘
- 구현
- function_template
- sort
- 예제
- sstream
- 백준
- 5397
Archives
- Today
- Total
- Today
- Total
- 방명록
어제의 나보다 성장한 오늘의 나
[c++][문제 풀이] 백준 18870번 <좌표 압축> 본문
반응형
문제 설명
입력된 값들 각각 자신 보다 작은 값이 몇 개 있는 지를 입력된 순서대로 출력 하면 되는 문제이다.
단 , 자신 보다 작은 값을 셀 때 중복 된 값들은 1개로 처리 된다.
문제 풀이
시간 제한은 2초.
입력 값은 0 ~ 10^6 까지 이다.
시간복잡도 O(N^2) 로는 풀 수 없고 O(NlogN) 으로 풀어야 한다.
algorithm 의 sort 함수 -> O(NlogN)
algorithm 의 lower_bound ->(O(logN) 함수 * N번) 를 사용할 것이다.
Coding
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int args ,char ** argv){
int N; // 좌표의 갯수
int X; // 좌표 값
vector<int> v; // 중복 제거 , 오름차순 정렬 할 벡터
cin >> N;
while(N--){
cin >> X;
v.push_back(X);
}
vector<int> v_before(v); // 입력 된 그대로의 벡터.
sort(v.begin() , v.end()); // 오름차순 정렬
v.erase(unique(v.begin() , v.end()), v.end()); // 중복 제거
vector<int> result;
for(int i = 0 ; i < v_before.size() ; ++i){
result.push_back(lower_bound(v.begin() , v.end() , v_before[i]) - v.begin());
}
for(auto x : result){
cout << x << ' ';
}
}
unique , lowerbound 함수에 대해 잘 모르겠다면 아래 글들을 참조 하자
2022.02.13 - [c++/문법] - [C++] Unique 함수 정리 및 예제
2022.02.13 - [c++/문법] - [c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제
백준 18870번 문제 링크
https://www.acmicpc.net/problem/18870
반응형
'c++ > 백준 문제 풀이' 카테고리의 다른 글
[c++][Greedy] 백준 10610번 문제 풀이 (0) | 2022.02.22 |
---|---|
[c++][Greedy] 백준 1789번 문제 풀이 (0) | 2022.02.22 |
[c++][Greedy] 백준 11399번 문제 풀이 (0) | 2022.02.20 |
[c++][Greedy] 백준 1541번 문제 풀이 (0) | 2022.02.19 |
[c++][Greedy] 백준 13305번 문제 풀이 (0) | 2022.02.19 |
Comments